8

N 2個の異なる整数のN行N列の配列aが与えられた場合、O（N）アルゴリズムを設計して、極小値を見つけます。次のようなインデックスiとjのペアです。

  • a[i][j] < a[i+1][j]
  • a[i][j] < a[i-1][j]
  • a[i][j] < a[i][j+1]
  • a[i][j] < a[i][j-1]

この質問は、オンラインアルゴリズムの本、Javaでのプログラミング入門、4.2章：並べ替えと検索で見つけました。

問題35（同じページ）に似ています：

  • N個の実数の配列が与えられた場合、対数時間で極小値（のようなインデックスia[i-1] < a[i] < a[i+1]）を見つける静的メソッドを記述します。

それは私が見つけることができないある種の二分探索ベースの解決策を持っています。

4

3 に答える 3

6

同じ問題が、Robert Sedgewick と Kevin Wayne による本 Algorithms の Web バージョンで言及されています。(「創造的な問題」セクション、問題 19 を参照) .

そのリンクで著者によって与えられた問題のヒントは次のとおりです。

行 N/2 で最小値を見つけ、列の隣接 p と q をチェックします。p または q が小さい場合は、その半分で繰り返します。

より良いアプローチは次のとおりです。行N/2で最小値を見つけ、その列のすべてのエントリをチェックし、列のエントリが小さい場合は、小さい列のエントリが属する行で繰り返します。

例えば。以下の配列では、N=5:

1  12  3   1  -23  
7   9  8   5   6
4   5  6  -1  77
7   0  35 -2  -4
6  83  1   7  -6

ステップ 1: 中段は [ 4 5 6 -1 77] です。すなわち。行番号 3。

ステップ 2: 現在の行の最小エントリは です-1。

ステップ 3: 最小エントリ (つまり-1) の列近傍は5と-2です。-2最小の隣人です。4行目にあります。

local minが得られるまで、手順 2 ～ 3 を続けます。

編集：

たとえば、@anuja からのコメントで言及されています (主な問題は n 行 n 列の配列です。この入力は 3 行 4 列の配列ですが、それで作業できます)。

1 2 3  4 
5 1 6 -1
7 3 4 -2

ステップ 1: 真ん中の行は[5 1 6 -1]です。すなわち。行番号 2。

ここに画像の説明を入力

ステップ 2: 現在の行の最小エントリは です-1。

ここに画像の説明を入力

ステップ 3: 最小エントリ (つまり-1) の列近傍は4と-2です。 -2最小列隣接です。3列目です。

ここに画像の説明を入力

ステップ 2 への反復: -2 は、その行で最小であり、隣接する列の中で最小です。したがって、極小値の出力として -2 で終了します。

ここに画像の説明を入力

于 2012-04-08T16:37:44.420 に答える
5

更新：この回答は、元の問題ステートメントの4つの比較によってエッジがそのように定義されていないため、エッジが極小ではないことを前提としています。この場合、この答えは正しいです (不可能です)。エッジが局所的最小値になるように質問を再定義すると、すべての行列に少なくとも 1 つの局所的最小値が含まれるため、分割統治法を使用できます。

エッジ セルが極小値にならない場合:

述べたように、質問に対する解決策はありません。N 行 N 列の配列では、要素を読み取るだけで O(N^2) 時間かかります。マトリックス内のどこにでも「隠れている」単一の極小値が存在する可能性があるため、これを行う必要があることが証明されています。

O(N^2) アルゴリズムを要求するつもりなら、単純に各要素を調べて、それをその 4 つの隣接要素と比較するのに O(N^2) 時間がかかります。

インタビューの質問を間違って覚えているか (それ以上の質問がありました)、これは単純なコーディングの演習にすぎません。

証明:

1. Construct a NxN matrix such that each cell has the value M[i,j] = N*i + j.
2. Select a random x,y (1 < x < N and 1 < y < N) and assign M[x,y] = -1

この行列には 1 つの極小値 (M[x,y]) があり、その位置は他のセルの値とは無関係です。したがって、他のセルはその位置に関する情報を提供しないため、予想される (N^2/2) セル = O(N^2) よりも優れたセルを検索するシステムを持つことは不可能です。

(つまり、最小値の M[x,y] = -1 を除いて、ほぼすべてゼロの行列 M[i,j] = 0 を検索することもできます。)

この証明は、ステップ 1 で局所的最小値を持たない行列を構築できるかどうかに依存します。 エッジ セルが可能な場合、すべての行列が局所的最小値を持たなければならず、この証明はもはや成立しません。

于 2012-04-08T13:51:21.767 に答える
2

ランダムなセルにアクセスします。その 4 つの隣接セルのいずれかがより小さい値を持っている場合: そのセルに移動します。隣人がそれよりも小さい場合は、ローカル ミニマムにいます。値が等しいセルが可能である場合、ループを回避するのは少し難しくなります。

アップデート：

1 つの隣人を訪問する代わりに、最小の隣人を選ぶことができます。

最も難しいトポロジーは、2 つの「同心」らせんの場合で、そのうちの 1 つはらせん状の堤防として機能します。最悪の場合でも、約 N/2 ステップかかります。(N=セル数)

于 2012-04-08T14:07:30.503 に答える