これは少し前に出てきた面白い質問です。サイズnの配列にm個の整数がありません
それから欠落M整数で番号1,2 ..、N + M 、と共に格納サイズNのソートされていない整数配列があります。 MおよびNは手前で知られている。最も効率的な方法で、欠損したMの整数を見つけるアルゴリズムを書く。 、
インデックス番目I値Iを持つ要素を含むように、サイズN + Mのアレイへのマッピングにそれをしようとしたが、これは2回の走査（マッピングの1を必要とします1 Mの番号が見つからない場合）。
私はこれに出くわした本は単一のスキャン解決策を言いますが、私はそれに到着することができませんでした。これについてどうやって行くかについてのアイデア？
これは、配列の上にマップされた二重リンクリストで行うことができます。各入力番号に対応した位置に入力あなたのインデックスを通るパスで
position 1 2 3 4 5 6 ...
next 2 3 4 5 6 7 ...
prev 0 1 2 3 4 5 ...
とリンクされたリストから（スキップ）、その位置を除去するためにリンクされたリストを更新します。入力の最後に、リンクされたリストには訪問していない位置のみが含まれます。
しかし、欠落している整数を印刷するためにリンクリストをループする必要はありませんか？私が理解しているように '> 1'ループですか？ – irrelephant
@irrelephantあなたがそれらを印刷したいと思うならば、あなたは賭けます。私は 'O（N）+ O（M）'という時間の複雑さの観点から、あなたが 'N 'の終わりに達するまで' Mの最後の行方を知ることができないので、 '。すでに印刷を開始していた場合は、最後に 'N'が出力されたものを含むことで、出力を損なう可能性があります。私はあなたがおそらく、より複雑な空間の視点から、M << N、[上記のコメントにリンクされている（印象的な見た目の数学的な答え）]（http://stackoverflow.com/a/3492967/1756702）そうしているようだ。 –
Big-O表記を使ってはいけません。私はあなたが 'M 'を印刷したいなら' N'と 'M'を一回通過するよりもうまくできないとは思わないと言っていました。 –
1スキャンアルゴを書き留めてください。ありがとう。 –
この質問は非常にローカライズされているようで、問題を自分で解決しようとしたという証拠は何も提示していません。 – lockstock
@ロックストックそれを残念。私は質問を編集しました。お役に立てれば。 – sanz