今日、面接で次のような質問を受けました。
重複を含まず、値が左から右、および上から下に増加する整数の n 行 n 列の配列が与えられた場合、指定された値が配列内にあるかどうかをチェックするアルゴリズムを提供します。
私が提供した答えは、このスレッドの答えに似ていました:
アルゴリズム: 2 次元整数配列で整数を検索する効率的な方法?
この解は O(2n) であり、私はこれが最適な解であると信じていました。
しかし、インタビュアーは、この問題をサブリニア時間で解決できると教えてくれました。これを行う方法について頭を悩ませましたが、何も思いつきません。
サブリニアソリューションは可能ですか、それともこれが最適なソリューションですか?
自問すべきことは、それぞれの比較からどのような情報が得られるかということです。「左上」または「右下」の長方形を削除できます。
「x」で比較すると、探しているものが大きいことがわかります。
XXX... XXX... XX × ... …… ……
'x' - チェックされたスペース
'X' - チェックは、これがデータの可能な場所ではないことを示しました
'.' - まだ不明
この情報をスマートな方法で使用して、長方形全体をチェックする必要があります。
中央の列でこのように二分探索を行うとします...
次のような結果が得られます
XXX... XXX... XXX... XXXXXX ...XXX ...XXX
2 つの長方形のスペースは、半分の幅と、場合によっては全高が残っています。この情報で何ができますか?
'.' の結果として得られる 2 つのサブ長方形を繰り返すことをお勧めします。 しかし、今では中央の列を選択する代わりに、中央の行を選択してバイナリ検索を実行します。
したがって、N x M の長方形の実行時間は、T(N, M) = log(N) + T(M/2, N)*2 のようになります。
再帰スタックが列と行のチェックを切り替えるため、インデックスの変更に注意してください。最終的な実行時間 (私は再帰を解いていませんでした) は、T(M, N) = log(M) + log(N) のようなものになるはずです (おそらくこれとまったく同じではありませんが、似ているでしょう)。