algorithm - mxnのオーダーのソートされた行列からN番目の最大値を見つける方法

Question

n 行 m 列の整数の行列で、行と列の両方の要素が減少しない順序で並べ替えられます。配列の N 番目の最大値を見つける最良の方法は何ですか? たとえば、指定された行列が 4x5 の場合

1  4  5  7
2  6  8  9
10 14 19 23
12 23 33 60
15 24 35 72

行列から 3 番目の最大値、つまり 35 を見つけます。

Answer 1

行列の各行を並べ替えられた配列として見て、N 番目の要素が見つかるまで、各配列で右から左に m 方向のマージを実行します。時間計算量は O(N*logm) になります。

vbmaster が提供する回答が正しいとは思いません。反対角レベルが常に左上のレベルよりも大きいとは限りません。次の例を検討してください。

1 2 3
3 4 5
7 8 9

vbmaster によって提案された順序を使用します。次のようになります: {9},{8,5},{7,4,3},{3,2},{1} ただし、3 番目のセット {7,4 ,3} には 2 番目のセット (7>5) よりも大きい要素があります。この順序を使用して 3 番目の要素を見つけると、答えは 5 になります。でも正解は7です。