11

リンクされたリストの中間ノードを可能な限り効率的な方法で見つけたいとします。与えられた最も典型的な「最良の」答えは、中間と現在の 2 つのポインターを維持することです。そして、遭遇した要素の数が 2 で割り切れる場合に中間ポインタをインクリメントします。したがって、1 回のパスで中間を見つけることができます。効率的ですよね？最後まで 1 回パスしてから、サイズ/2 に達するまでさらに 1 回パスするブルート フォースよりも優れています。

しかし...それほど速くはありません.最初の方法が「ブルートフォース」方法よりも速いのはなぜですか? 最初の方法では、中間ポインターを約 size/2 倍にインクリメントしています。しかし、強引な方法で、2 番目のパスでは、サイズ/2 番目のノードに到達するまでリストをトラバースしています。これら2つの方法は同じではありませんか？1 番目が 2 番目よりも優れているのはなぜですか?

//finding middle element of LinkedList in single pass
          LinkedList.Node current = head;
          int length = 0;
          LinkedList.Node middle = head;

          while(current.next() != null){
              length++;
              if(length%2 ==0){
                  middle = middle.next();
              }
              current = current.next();
          }

          if(length%2 == 1){
              middle = middle.next();
          }
4

5 に答える 5

8

コードを次のように変更すると:

      while(current.next() != null){
          current = current.next();
          middle = middle.next();
          if(current.next() != null){
              current = current.next();
          }
      }

lengthをインクリメントする必要がないため、割り当てが少なくなりました。これにより、同じ結果が得られると思います。

結局のところ、両方のソリューションは O(N) なので、マイクロ最適化です。

于 2013-06-25T23:44:32.607 に答える
4

@Oleg Mikheevが示唆したように、次のように、 Floyd のサイクル検索アルゴリズムを使用して中央の要素を見つけられないのはなぜですか。

private int findMiddleElement() {
        if (head == null)
            return -1; // return -1 for empty linked list
        Node temp = head;
        Node oneHop, twoHop;
        oneHop = twoHop = temp;
        while (twoHop != null && twoHop.next != null) {
            oneHop = oneHop.next;
            twoHop = twoHop.next.next;
        }
        return oneHop.data;
    }
于 2016-01-16T12:51:48.923 に答える
1

最初の答えには複数の利点があります。

  1. 2 つの方法は同じ複雑さ O(N) であるため、特定の実装とコスト モデルが関係する可能性があるため、効率に関する分析には注意が必要です。ただし、最も単純な実装では、最初の方法でループ変数のインクリメントを節約できます。

  2. 1 つの変数のスペースを節約します - 2 つのポインターと長さ、カウンターと 1 つのポインター。また、巨大なリストで、長さがオーバーフローした場合はどうなりますか?

ただし、特定のモデルを検討する場合は、2 番目の方法の方がはるかに優れている可能性があります。要素がすべてメモリ内で隣接しており、リストが十分に大きい場合、キャッシュは連続メモリを 1 か所しか保持できず、最初の方法ではメモリ アクセス コストが発生する可能性があります。結局のところ、これら 2 つの方法はほとんど同等です。もちろん、最初の方法で使用されるテクニックはより派手であり、思考プロセスは他のコンテキストで役立つ場合があります.

于 2013-06-25T23:47:55.230 に答える