HWについてこの質問を受けましたが、その方法がわかりません。
配列A [1 ... n]には、1つを除く0からnまでのすべての整数が含まれています。配列はソートされていません。
この問題では、1回の操作でAの整数全体にアクセスすることはできません。
Aの要素はバイナリで表され、それらにアクセスするために使用できる唯一の操作は「A [i]のj番目のビットをフェッチする」であり、これには一定の時間がかかります。
O（n）時間で欠落している整数を見つけなければなりません。
モーマルに実行するのにかかる時間はO（NlgN）です（N配列で実行し、N-lgnビットの関数であるすべてのビットをフェッチします）。
すべてのビットを読み取らずにそれを行うにはどうすればよいですか？
今のところ、ある k に対して n が 2^k - 1 であると仮定しましょう。
k = 3 の例も見てみましょう。
000
001
010
011
100
101
110
111
上記のような完全なセットがある場合、各列 (各桁の位置) に同じ数の 1 と 0 があることに気付くでしょう。もちろん、便宜上、これをソート済みとして表示していますが、実際にはソート済みであるとは述べていません。
次のリストを見てみましょう
000
001
010
011
100
110
111
すべての要素 ( O(n) ) の最初のビットを見て、どのカウントが他のカウントよりも小さいかを判断します。
最初のビットには、最上位ビットの 1 が欠落している数値があることがわかります。これは、数値の最上位ビットが 1 であることがわかっていることを意味します。
基本的に、最上位ビットが 1 のセットと最上位ビットが 0 のセットの 2 つのセットに分割します。小さい方のセットは、欠落している数値のビットを示します。
小さい方のパーティションでも同じことを行います。
O(n) + O(n/2) + O (n/4) ですので、基本的には O (2n) が O (n) です。
編集
一般的なケースについては、次の文書の 1 ページの下部を参照してください。
基本的には、n が 2 の累乗でない場合、n が与えられた場合、ビット = 1 パーティションとビット = 0 パーティションに該当する数が正確にわかるという事実を考慮することができます。これは完全なセットでした。