1

長さが不明な片方向リストがあるとします。テールまで M ステップのノードを見つけたいとします。

たとえば、単独のリストは次のようになります: (A)->(B)->(C)->(X)->(Y) および M = 2. この場合、出力は (C) へのポインターになります。

このクイズに直面したとき、私の最初の反応は、単一リンク リストをトラバースして長さ N を取得することです。次に、2 回目は単一リンク リストをトラバースしますが、NM-1 ステップだけを進めます。時間の計算量は O(n) で、空間の計算量は O(1) です。

次に、ワントラバース方式でそれを行うための解決策を見つけることに挑戦します。解決策は、2 つのポインタを持つことです。2 番目のポインターは、最初のポインターより M ステップ遅れています。これらの 2 つのポインターは、同じペースで前進します。最初のポインターが末尾に到達すると、2 番目のポインターが結果になります。

この質問について深く考えてみた結果、2 番目の「トリッキーな」解決策が最初の解決策よりも優れているとは思えません。これは 1 回のトラバースですが、2*NM ポインターの割り当ても伴います。

この質問について考えたことはありますか？本当に高速な他のソリューションはありますか?

4

5 に答える 5

3

循環バッファを使用する必要があります

M + 1 ポインターの配列を割り当て、リストの各ノードの (i mod M + 1) 番目のポインターを埋めます。最後に到達したら、配列内で M を振り返ります (必要に応じてラップアラウンドします)。

そうすれば、書き込みは N 回しかありません!

C++ のハック ジョブ サンプル プログラムを次に示します。

node* get_Mth_from_end(node* head, int m)
{
  int pos = 0;
  node** node_array = new node*[m + 1];
  node_array[0] = head;
  while (node_array[(pos + 1) % (m + 1)] = node_array[pos % (m + 1)]->next)
     pos++;
  if (pos < m)
  {
     delete[] node_array;
     return NULL;
  }
  pos = pos - m;
  if (pos < 0)
     pos = pos + m + 1;
  node* retval = node_array[pos];
  delete[] node_array;
  return retval;
}

これは、1 エラーでオフになっていることを確認する必要があります。私のポインター構文も少しずれているかもしれませんが、アイデアはそこにあります。

于 2009-01-20T04:49:20.627 に答える
0

私は再帰的な提案が好きです。ただし、問題のダブルポインターアルゴリズムよりもパフォーマンスが向上するとは思いません。

データ構造がより高速な操作をサポートしていないという点で、Rubancache は正しいです。トラバーサルは低速ですが、挿入時間は高速です。

于 2009-01-20T04:46:50.320 に答える
0

N+4M のポインター割り当てと log(M) スペースで実行できます (余分なスペース、リストは既に N を占有しています)。方法は次のとおりです (この考え方は、ゴーバック デバッガーで使用される考え方と同じです)。疑似コードが続きます。ここで、M < 2^m であり、p は長さ m の循環バッファーです。

for (n=0, front = 0; p[front] != end; ++n, ++p[front]) {
  for (j = 0; j < m; ++j)
    if (n % j = 0)
      ++ front
  front = front % m
}
front = (front-1) % m
for (j = M; j < n-2^m - (n mod 2^m); ++j)
  ++p[front]

p[front] があなたの答えです

于 2009-01-20T08:51:44.037 に答える
0

提案されたカウントスタイルのアルゴリズム以外に、次のような再帰関数を使用できます。

int getNumNodesAfter(Node *node){
   if( node->next == NULL ){
      return 0;
   }else{
      return getNumNodesAfter(node->next) + 1;
   }
}

もちろん、関数が探している数値を返したときに問題のノードを格納するための適切な方法を見つける必要があります。

(編集: これはおそらくカウント アルゴリズムよりも効率的ではなく、単なる代替手段です)

ただし、この質問に対する本当の答えは次のとおりです。データ構造 (単方向リンク リスト) では、実行したい操作の高速な実装が容易ではないため、新しいデータ構造を選択する必要があります。

于 2009-01-20T04:42:56.850 に答える
-1

もう少し良いものは次のようなものになると思います：

FindNFromEnd(head, n)
    counter = 0;
    first = head
    firstplusn = head
    while (head.next != null)
        counter++
        head = head.next

        if counter == n
            first = firstplusn
            firstplusn = head
            counter = 0

     while counter < n
         counter++
         first = first.next

     return first

たとえば、n = 3 の場合、次のようになります。

    0   1   2   3   4   5   6   7
1   FNH
2   FN  H   
3   FN      H
1   F           NH 
2   F           N   H
3   F           N       H
1   F           N           H
2               F           N   H
---
3                  [F]

したがって、F は head - N - counter を追跡し、N は head-counter を追跡し、O(2*N - M) ではなく (N + M + N/M) を実行するだけで済みます。

于 2009-01-20T06:26:23.753 に答える