問題1. 1からnまでの自然数を含む長さ（n + 1）の配列Aがあるとします。 配列を変更したり、追加のメモリを使用したりせずに、O（n）時間内に繰り返し要素を見つけます。
すぐに説明します。 条件は、配列内に1からnまでのすべての数値が見つかったとは言っていないので、好きなだけ多くの繰り返し要素が存在する可能性があります（すべての数値が1回で、2回に1回であれば、タスクははるかに単純になります）。 追加メモリの使用に関する制限は、線形長の追加配列を開始できないが、変数を開始できることを意味します。
問題2.ペアごとに異なる自然数を含むnxn行列が与えられます。 時間O（n）の極小値を見つける必要があります。
行列の極小値は、その4つの隣接要素すべてよりも小さい要素です（この要素が境界にある場合は3、角度要素の場合は2）。 nの行列で2次の要素数が必要ですが、n時間で線形である必要があることに注意してください。 したがって、マトリックスは既にメモリに読み込まれていると仮定します。 そして、そのセルの線形数にのみ目を向けて、その中で極小値を見つける必要があります。
カットの下-最初の問題の解決策。 もう一度問題を解決してから猫の下を見るようにお願いします。 2番目のタスクでは、何らかのヒントを言うことができます。
解決策だけでなく、どのように推測できたかをお伝えします。 例ですぐに説明します。 それから、一般的なケースでアルゴリズムがどのように機能するかが明確になることを願っています。 作業例：
つまり、1〜8の数字を含む長さ9の配列が与えられ、2つまたは5つの値を見つけることが目標です。
覚えているように、タスク条件で追加のメモリを使用することは禁止されています。 しかし、彼女がどのように私たちを助けることができるかを理解しましょう。 次に、サイズnの新しい配列を開始し、元の配列Aを1回パスすることで、1からnまでの各数値がAにある回数を計算します。この配列から、Aの誰が繰り返されているかがすぐにわかります。
これは将来的にはあまり役に立ちませんが、それでもです。
追加メモリの制限により、アレイに関する補助情報を収集および記録することはできません。 そのため、配列を何とか「歩いていく」繰り返し要素を見つける必要があります。 たとえば、配列を左から右にウォークスルーできますが、どの情報を抽出できるかは明確ではありません。 したがって、私たちは別の方法で歩こうとします。 配列の最初の要素に入り、そこに何が書かれているのか見てみましょう。 番号7が書き込まれているので、配列の7番目の要素を見てみましょう。 そこには数字の1が書かれています。 配列にいくつかのループがあるという事実は、将来的に非常に役立ちます。 たとえば、2番目の要素から見てみましょう。そこから要素番号5に進み、そこから要素番号3に進み、要素3から再び要素番号2に戻ります。つまり、別のサイクルが見つかりました。 見つけた2つのサイクルを描いてみましょう。
そして、配列が暗黙的に特定のグラフを定義していることに気付いたので、このグラフを明示的に描画しましょう。 正式には、グラフの頂点は1〜n + 1の数字です。 A [i] = jの場合、iからjへの指向エッジを描画します。
少なくとも2つのエッジを含むこのグラフの頂点に興味があります（頂点iとkからのエッジが頂点jに入る場合、A [i] = A [k] = j、つまりjは配列Aで繰り返されます）。 グラフにはこのような頂点があることはすでに明らかですが、グラフの観点からこれをもう一度理解しましょう。 グラフでは、各頂点から1つのエッジが出ています（したがって、グラフ（n + 1）、エッジ）。ただし、頂点は何も含まれていません。頂点（n + 1）です。 したがって、少なくとも2つのエッジを含む頂点があります。 一般に、これはすでに明らかでしたが、トップ（n + 1）についての発言は将来的に役立ちます。
最上部（n + 1）に移動して、グラフの出力エッジを調べてみましょう。 もちろん、いつかはサイクルになりますが、重要なことは、トップ（n + 1）に戻らないことです。 作業例では、頂点9を終了し、サイクル（5,2,3）に到達します。 このサイクルへのエントリポイントは繰り返し要素であることがわかります。結局、このポイントはサイクルのエッジに沿って、また頂点（n + 1）からサイクルへのパスに沿ったエッジに沿って入力できます。 この例では、このようなエントリポイントは頂点5です。
この点を見つけることは別の簡単なタスクではありませんが、その解決策は標準のリストループの問題を解決することに非常に似ています。 サイクルの長さを見つけることは難しくありません。 たとえば、頂点n + 1からn + 1ステップを取得します。 その後、私たちは確かにサイクルのトップになります。 このピークを思い出し、そこに戻るまで歩き続けます。 したがって、サイクルkの長さがわかります。 次の操作を行います。 頂点n + 1に2つのポインターを置きます。 最初のポインターはkステップを実行します。 その後、各ポインターを、それらが出会うまで1ステップ先に移動します（したがって、最初のポインターは常にkステップで2番目のポインターを追い越します）。 これらの人たちが私たちが必要とするエントリーポイントで会うことは明らかです。 この例では、サイクルの長さは3です。 3ステップ後、最初のポインターは頂点2になります。この時点で、2番目のポインターの移動を開始します。 2つのステップの後、ポインターは頂点5で交わります。
おやつに。 配列の変更が禁止されている理由については説明しませんでした（そして、配列は実際にはアルゴリズムに触れませんでした）。 アレイを損なうことが許されている場合は、より簡単なソリューションを考えてください。