平平淡淡从从容容

0%

查找算法

发表于 分类于 339 1 分钟

飞雪连天射白鹿，笑书神侠倚碧鸳。

一、七大查找算法

  1. 顺序查找
  2. 二分查找
  3. 插值查找
  4. 斐波那契查找
  5. 树表查找
  6. 分块查找
  7. 哈希查找

二、实战

  1. 单链表取中间节点

    • 单向链表(单链表)是链表的一种，是由一系列的存储数据元素的单元(通常称为结点node)通过指针串接起来形成的，每个单元至少有两个域，一个域用于数据元素的存储，另一个域是指向其他单元的指针。

    • 特性

      • head指针指向第一个结点(表头结点)，最后一个节点的next指针为null
      • 在已知待操作结点位置的情况下，插入和删除的时间复杂度是O(1)

    • 实现

      • 方案一：遍历整个单链表，得到链表的长度length，length/2即为单链表的中间结点。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      function getMiddleNode($head) {
          if ($head == null || $head->next == null){
              return $head;
          }

          $prev = $head;
          $size = 0;
          while($prev) {
              $size++;
              $prev = $prev->next;
          }
          
          $position = (int)($size/2);
          while($position--) {
              $head=$head->next;
          }

          return $head;
      }
      • 方案二：设置两个指针i和j，i一次走一步，j一次走两步，当j到达链表尾的时候，i所指向的结点就是单链表的中间结点。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      function getMiddleNode($head){
          if ($head == null || $head->next == null){
              return $head;
          }

          $p1 = $head;
          $p2 = $head;

          while($p2->next != null && $p2->next->next) {
              $p2 = $p2->next->next
              $p1 = $p1->next
          }

          return $p1;
      }

三、参考