5

これは私が少し前に出くわした興味深い質問で、解決するのに苦労しました。

番号1,2..,N+M で格納されたサイズNのソートされていない整数配列があり、 M個の整数が欠落しています。MとNは事前にわかっています。欠落しているM個の整数を最も効率的な方法で見つけるアルゴリズムを作成してください。

サイズN + Mの配列にマッピングして、i番目のインデックスに値iの要素が含まれるようにしようとしましたが、これには 2 回のスキャンが必要です (マッピングに 1 回、欠落しているM個の数値を見つけるのに 1 回)。

私がこれに出くわした本は、単一のスキャンソリューションが可能であると述べていますが、私はそれに到達できませんでした. これについてのアイデアはありますか？

4

1 に答える 1

1

これは、配列の上にマッピングされた二重リンクリストを使用して行うことができます。

position 1 2 3 4 5 6 ...
next     2 3 4 5 6 7 ...
prev     0 1 2 3 4 5 ...

入力を通過するときに、各入力番号に対応する位置にインデックスを付け、リンクリストを更新して、リンクリストからその位置を削除（スキップ）します。入力の最後に、リンクリストには訪問されていないポジションのみが含まれます。

于 2012-11-09T03:40:11.043 に答える