1

行と列でソートされたマトリックス。Kth与えられた行列から最小の要素を見つける必要があります。

時間の複雑さを伴うソリューションがありますが、問題に対する線形時間アルゴリズムO(KlogM)が必要です。

マトリックスの例: 

1   3    5
2   4    6
7   8    9

M = 行数、N = 列数、およびM<N.

私の解決策：

  1. matrix[i][0]すべての要素を取得してサイズ M のヒープを作成します。
  2. 最小の要素を見つけて、対応する行から次の要素をプッシュします。
  3. Kth最小になるまで 2 番目のステップを繰り返します。
4

2 に答える 2

4

Frederickson and Johnson アルゴリズムは、おおよそ次のように機能します。(いつも思い出すのはQuickselectです。) これは、別の実装をテンプレートとして使用した実装からのものであるため、詳細は彼らの論文とは少し異なる場合がありますが、同じ時間の複雑さと同じ考え方です。krun from 0toの正当な値を想定していますM * N - 1。

(0 から数えて)番目のi行とj番目の列の要素にアクセスします。A[i, j]さらに、A[i, -1]どちらが負の無限大で、A[i, N]どちらが正の無限大であるかにアクセスできると仮定します。次のプロパティを持つインデックスleft[0 .. M)との 2 つの配列right[0..M)、および 2 つの変数lessthanleftとを維持します。greaterthanright

  • 行列要素が存在するA[i0, j0]ため、すべての行iで が得られA[i, left[i] - 1] < A[i0, j0] <= A[i, left[i]]ます。つまり、left[i]おおよそ、A[i0, j0]それが row にある場合の位置iです。
  • からまでの値の合計left[i]はです。は、 で示される位置の左側の位置にある行列要素の数です。つまり、厳密に 未満の行列要素です。i0M - 1lessthanleftlessthanleftleftA[i0, j0]
  • lessthanleft <= k. これは、探している要素がiの右側の行にあることを示していますleft[i]。
  • 行列要素が存在するA[i1, j1]ため、すべての行iで が得られA[i, right[i] - 1] < A[i1, j1] <= A[i, right[i]]ます。つまり、right[i]おおよそ、A[i1, j1]それが row にある場合の位置iです。
  • からまでの値の合計N - right[i]はです。は、 で示される位置の右側の位置にある行列要素の数です。つまり、厳密に よりも大きい行列要素です。i0M - 1greaterthanrightgreaterthanrightrightA[i1, j1]
  • greaterthanright <= M * N - k. これは、探している要素がiの左側の行にあることを示していますright[i]。

これらのプロパティは、 to のすべての要素、leftto0のすべての要素、およびrighttoNの両方を設定することによって初期化できます (この場合は を返します) または(この場合は を返します)。ちなみに、これは 、 、 、 に対応します。lessthanleftgreaterthanright0k = 0A[0, 0]k = M*N - 1A[M-1, N-1]i0=0j0=0i1=M-1j1=N-1

ここで、すべての反復で、ピボット マトリックス要素をA[i2, j2]で選択しleft[i2] <= j2 < right[i2]ます。(いくつかの戦略があります。これについては後で説明します。) 配列less[0..M)とを使用lessequal[0..M)して、次の内部ループに入力し、変数nlessおよびnequalをngreaterに設定します0。内側のループでは、すべての行を反復処理しi、 and を設定less[i]しlessequal[i]て、 A[i, less[i] - 1] < A[i2, j2] <= A[i, less[i]]andを設定しA[i, lessequal[i] - 1] <= A[i2, j2] < A[i, lessequal[i]]ます。(とless[i-1] >= less[i]の値を使用して、そこから左に線形探索を開始すると、全体的に時間がかかります。) このような各ステップの後、 に追加し、 に追加し、 に追加します。less[i-1]lessequal[i-1]O(N)less[i] - left[i]nlesslessequal[i] - less[i]nequalright[i] - lessequal[i]ngreater

この内側のループの後、 かどうかを確認しますlessthanleft + nless >= k。この場合は、 beに設定して(配列のループでの割り当てを防止する場合はポインターのフリッピングを行うか、 から に値をコピーして)、beA[i2, j2]に設定するよりも少ないエントリを続行し、次の処理に進みます。反復。の場合、 beおよびbeに設定して次の反復を続行することにより、より大きいエントリを続行します。それ以外の場合、探しているエントリは に等しいエントリの中にあるため、 を返します。rightlesslessrightgreaterthanrightgreaterthanright + ngreater + nequallessthanleft + nless + nequal < kA[i2, j2]leftlessequallessthanleftlessthanleft + nless + nequalA[i2, j2]A[i2, j2]

次に、ピボットの選択についてです。c1 つの方法は、間隔で乱数を選択すること[0 .. N * M - lessthanleft - greaterthanright)です。次に、とcの間の 番目の行列要素を含む行を、から開始して負になるまで から減算することによって見つけます。負になる場所を選択して. または、各行の残りのエントリの中央値に対して中央値スタイルの計算を行うこともできます。leftrightleft[i] - right[i]ci0ij = round((left[i] + right[i])/2)

したがって、一般的に、各行の間にある行列要素のセットは分割され、できれば反復ごとに約半分になりleft[i]ます。複雑さの分析は、予想される反復回数が初期プール内の値の数で「ほぼ確実に」(数学的な意味で) 対数になるQuickselectright[i]の分析に似ています。中央値の中央値スタイルのピボット選択を使用することで、実際の実行時に支払いを行いながら確実にこれを達成できると思いますが、ここでは「ほぼ確実」で十分であると仮定します。(これは、Quicksort が O(N lg(N)) であるのと同じ条件です。) 個々の反復では、ピボットを選択するのに時間がかかり、次に内側のループで時間がかかります。候補者の初期プールはO(M)O(N)M*NO(lg(M * N)) = O(lg(M) + lg(M))メンバーなので、合計の複雑さに対して、反復回数はほぼ確実に ですO(N * (lg(M) + lg(N)))。すべての行のエントリでヒープを使用するアルゴリズムは、によってのみ制限されるO(k * lg(M))ため、さらに悪い結果になります。kN*M

簡単な例M=4を次に示します。N=5k=11A

 6 12 17 17 25
 9 15 17 19 30
16 17 23 29 32
23 29 35 35 39

、、および両方をに初期化leftします。[0,0,0,0]right[5,5,5,5]lessthanleftgreaterthanright0

最初の反復をA[1, 2]=17ピボットとして選択するとします。内側のループ中に、最初の行のエントリright[0]-1=4から左への調査を開始し、最大 である数値の最初の出現を見つけ17ます。これは列3にあるので、設定しlessequal[0]=3+1=4ます。厳密に より小さい数値の最初の出現を検索し続け17ます。これは列で発生する1ため、 を設定しless[0]=1+1=2ます。17次の行では、最大で columnにある値を探し始めることができ、lessequal[0]それを column 2so setで見つけますlessequal[1]=2+1=3。17から始まる値より厳密に小さい値を探してless[0]、 を設定しless[1] = 2ます。続けて と を取得less = [2,2,1,0]しlessequal = [4,3,2,0]ます。したがってnless = 5、、、nequal = 4_ngreater = 11. を持っているlessthanleft + nless + nequal = 9 < 11ので、 より大きい17と と を設定left = lessequal = [4,3,2,0]したエントリを続けますlessthanleft = 9。

次の反復では、とiの間の中央にある行のピボットを選択する必要がleft[i]ありright[i]ます。行 を選択2すると、 があることになりますA[2,3] = 29。内側のループ中に、less = [5,4,3,1]andとlessequal = [5,4,4,2]でnless = 4andを取得します。では、以下のエントリと setおよびのエントリを続けます。nequal = 2ngreater = 5lessthanleft + nless = 13 > 1129right = less = [5,4,3,1]greaterthanright = 7

3 回目の反復では、すべての行に 1 つのエントリしか残っていません。行をランダムに選択します - おそらく行3です。ピボットはA[3,0] = 23. 内側のループ中に、 と を取得less = [4,4,2,0]しlessequal = [4,4,3,1]ます。したがってnless = 1、nequal = 2、およびngreater = 1。を持っているlessthanleft + nless = 10 < k = 11 <= lessthanleft + nless + nequal = 12ので、 を返し23ます。実際、厳密に 10 個の行列エントリ23(A[i, less[i]]最後の反復で の左側にあるもの) と最大で 12 個の行列エントリ23(最後の反復で の左側にあるものA[i, lessequal[i]]) があります。

于 2013-09-26T20:29:44.947 に答える
-1

O(k)現在の最小値から次の最小値に「ジャンプ」して、ほとんどの操作を行うアルゴリズムを作成できると思いますk。そのために 2 つの参照を使用できます。1 つはすべての列の現在の最小値を示し、もう 1 つはすべての行の現在の最小値を示します。次に、各反復を行または列のいずれかで進めます。k回繰り返した後、目的の値に到達しKthます。

于 2013-09-26T13:34:44.537 に答える