1

重複の可能性：
リストにない最小の整数を見つける

ソートされていない正の整数のストリームがあります。ストリームからすべての数値を読み取った後、ストリームにない最小の正の整数を特定する必要があります。

例: 正の整数のストリーム: 6 7 8 9 1 2

答え：3

正の整数のストリーム: 1 2 3 4 5

および : 6

正の整数のストリーム: 12 87 899

答え：1

余分なデータ構造をとらずに問題を解決したかったのです。出来ますか？

私はこの問題で立ち往生しています。インターネットでできる限りの調査を行いましたが、うまくいきませんでした。誰でも助けてくれますか。

4

2 に答える 2

1

挿入ソートを使用して読み取るときに配列をソートし (データがストリームからどのように取得されるかを見て、これは効率的である必要があります)、それを反復処理できます。が欠落している場合1、それがあなたの答えです。そこにある場合は、次の整数が配列内の次の数値であるかどうかを繰り返し確認できます。そうでない場合、次の整数は欠落している整数です。

于 2012-12-20T13:48:19.440 に答える
0

次の 2 つの制約を満たす場合の方法があります。このアルゴリズムはストリームを 2 回スキャンし、256KB のメモリを必要とします。

  1. 各要素は以下です0xFFFFFFFF。
  2. ストリーム内のすべての要素は個別です。

以下は、このアルゴリズムを示しています。

  1. 配列を割り当てます: unsigned int bucket[2^16].
  2. このストリーミング データをスキャンします。現在のデータがaの場合、bucket[a>>16]++;
  3. このストリームをスキャンした後、値が より小さい最初のバケットを見つけ2^16ます。最初に見つからない符号なし整数がこのバケットにあります。このバケットのインデックスをkとし、残りの最初の符号なし整数を としますn。それからk*(2^16) <= n < (k+1)*(2^16)。
  4. すべてのバケットの値をゼロにリセットします。
  5. このストリーミング データを再度スキャンします。現在のデータがaとk*(2^16) <= a < (k+1)*(2^16)の場合、bucket[a&0xFFFF]++.
  6. このストリームを再度スキャンした後、値がゼロの最初のバケットを見つけます。このバケットのインデックスを としますh。

  7. この答えn = k*(2^16) + h。

    注: 3 番目のステップのバケット [0] は、符号なし整数のセットに 0 が含まれていないため2^16 - 1ではなく、最大である必要があります。2^16

    　　ˊ

于 2012-12-20T19:30:09.473 に答える