c# - 2Dソートされた配列でk個の最小/最大要素を見つけます

Question

2D配列が与えられます。行と列が並べ替えられます。

最も効率的な方法で、2次元配列からk番目に大きい要素を見つけます。その場で行うことはできますか？

Answer 1

ややブルートフォースのインプレースソリューション：バイナリ検索で値を推測してみてください。あなたは最大値と最小値を知っています（それらは隅にあります）。すべての候補について、小さい要素と大きい要素の境界をたどりながら、小さい要素の数を数えます。配列はソートされているため、この境界はそれを横切る適度に短いパスです。小さい要素の中で最大の位置を追跡します。この値は数回表示される場合があります。それらを数える。NxN配列を想定すると、これはO（N * B）を取ります。ここで、Bは値のビット数です。

私はただ大声で考えています...信じられないほど最適な解決策について読んだことを漠然と覚えていますが、どこにあるのかわかりません。