3

Programming Pearls 2nd Editionという本から、コラム2のセクション2.1の質問Aを引用します

ランダムな順序で最大 40 億の整数を含むシーケンシャル ファイルが与えられた場合、ファイルにない 32 ビット整数を見つけます (少なくとも 1 つ欠落している必要があります - なぜですか?)。十分な量のメイン メモリを使用して、この問題をどのように解決しますか? いくつかの外部「スクラッチ」ファイルを使用できるが、メインメモリは数百バイトしか使用できない場合、どのように解決しますか?

問題文には、「最大で」40 億個の整数があると書かれています。したがって、1 つの有効な入力が 100 から 299 の範囲にあり、1 つの数値が欠落している可能性があります。この問題ステートメントの理解が正しければ、この問題に必要な入力は、数字を含むファイルと、ファイル内の数字の範囲、つまり i から n です。

この問題については、次の O(n) ソリューションは、本 (Ed Reingold から) で与えられたものよりも直感的ではありませんか? または、何か不足していますか？

指定された範囲が i...n であると仮定します

using the forumla (n * (n + 1) / 2) 
  x = the sum of numbers from 1 to i-1 
  y = the sum of numbers from 1 to n 
walk through the input and get a sum of the numbers (value z)

missing number = (y - x - z)
4

1 に答える 1

4

あなたは何かが欠けています:

  1. 数値は一意であるとは言えません。合計のアプローチでは、一意の要素と、範囲内で欠落している要素が 1 つだけであると想定されます。
  2. 数値の範囲はわかりません.32ビット整数では、4Bよりもはるかに多くの要素を持つことができます（正確には、4Bよりも32ビットで表現できる数値が294967296あります）

で単純化されたカウンターの例を見てくださいrange = [1,5], array = [5,5,5,4,1]。
この場合、 が得られx=1, y = 15, z = 20ます。
しかし、20-15-1 = 4欠品ではありません。

この場合に実行されるradix sortを使用O(n)して (32 ビットは定数であるため)、ソートされた配列をスキャンして、最初に欠落している要素を見つけることができます。

編集:それを行うためのより効率的な方法は、基数ソートと選択アルゴリズムのバリエーションを使用することです:

  1. 現在のビット数を としますk。最初のビットを見て、配列を 2 つの部分に分割します。最初の部分ではこのビットが設定されておらず、2 番目の部分ではこのビットが設定されています。
  2. パーツの少なくとも 1 つで、要素が少なくなければなりません(2^k) / 2 = 2^(k-1)。
  3. 問題をこのサブ配列のみにk' = k-1 減らして (現在のビット数を減らして) 使用し、1 に戻します。

ビットが尽きるまでそれを続けると、元のリストにない数値が得られます。

リストが十分にランダムであると仮定すると、アルゴリズムの複雑さはO(n)- 任意の数のビットに対して (ではないO(n*k))であることに注意してください。

于 2012-12-28T10:00:52.833 に答える