3

質問: 入力は順次ファイルにあります。ファイルには、最大で 40 億の整数が含まれています。欠落している整数を見つけます。

私の理解による解決策：

  1. 先頭が 0 の 2 つの一時ファイルと先頭が 1 の一時ファイルを作成する

  2. 2 つの MUST (4.3B ピジョンホールと 4B ピジョン) のうちの 1 つは 2B 未満です。ファイルを選択し、ステップ 1 と 2 を 2 番目のビットで繰り返し、次に 3 番目のビットで繰り返します。

この反復の終了条件は何ですか?

また、この本ではアルゴリズムの効率がO(n)であると言及されていますが、

1 回目の繰り返し => n 回のプローブ操作
2 回目の繰り返し => n/2 回のプローブ操作
.
.
.
n + n/2 + n/4 +... 1 => nlogn??

何か不足していますか？

4

2 に答える 2

4

両方のファイルをチェックして、要素が最も少ないファイルを選択します。

すべての 32 ビットを通過するまでこのプロセスを繰り返し、最後にファイル 0 要素を取得します。これは、欠落している数字の 1 つがあるはずだった場所です。したがって、これまでにフィルター処理したビットを追跡していれば、数値が何になるべきかがわかります。

これは(つまり「任意の」) 欠落している番号を見つけるためのものであることに注意してください。40 億 ((4294967296) ではない) 整数の (順不同) シーケンシャル リストが与えられた場合、2^32見つけなければならない 1 つの欠落がある場合、最初に欠落している整数を切り取ることができるため、これは機能しません。

また：

n + n/2 + n/4 + ... 1 <= 2n

違いn log nます。

これは の幾何学的数列でa = n, r = 1/2あり、次の式で計算できます。

n (1-(1/2)^m)
-------------
  1 - (1/2)

0 < (1/2)^m < 1任意の正の数m(以降)0 < 1/2 < 1については、次のように言うこと(1-r^m) < 1ができ、したがって、最大値は次のように言うことができます。

  n.1
-------
1 - 1/2

   n
= ---
  1/2

= 2n
于 2013-10-16T08:31:25.827 に答える