Intersection of Two Arrays

nums1の各値について、nums2を検索します。最初に一致したところで検索を止め、すでに答えに含まれている値はスキップするので、[8, 8, 8, 8]を[8, 8]と照合すると、4個ではなく8が1個得られます。最後に答えをソートします。

この方法が正しいのは、nums1内の値が、nums2内にあるその値のコピーのいずれかと一致した場合に限り、答えに追加されるためです。また、スキップすることで、同じ値が2回追加されるのを防ぎます。

この方法が遅いのは、nums1の各値について、nums2全体を検索する可能性があるためです。各配列に5000個の値がある場合、比較回数は最大で2.5 × 10^7回になります。また、大規模なテストでは一致する値が見つからないことが多いため、ほとんどの検索が最後まで続きます。

ソートすると、例1は[2, 2, 4, 6, 9]と[1, 4, 4, 6]になります。ポインターiを最初の配列の先頭に、jを2つ目の配列の先頭に置きます。小さい値を指すポインターを進めます。その値は、もう一方の配列のそれより後ろにあるどの値とも一致しません。そこにある値はすべて、それ以上の大きさだからです。両方のポインターが同じ値を指しているとき、その値は共通なので、それを追加して両方を進めます。

この例では、2 > 1のときjを進め、どちらの2も4より小さいのでiを進め、4 = 4のとき4を追加します。2つ目の4は6より小さいのでjを進め、6 = 6のとき6を追加します。[2, 2, 3]と[2, 2]にある2のように、両方に複数回現れる値は複数回一致します。直前に追加した値と比較することで、同じ値を1つだけ残します。結果は、追加の処理なしでソートされた状態になります。

ソートの計算量はO(n log n + m log m)で、走査の計算量はO(n + m)です。各ステップで少なくとも片方のポインターが進むためです。多くの実装ではコピーをソートするため、O(n + m)のメモリを消費します。入力を並べ替えてもよい場合は、Cコードのようにその場でソートすれば、追加メモリは答えを格納する分だけです。

nums1 のすべての値をハッシュセットに入れます。例1では、セットは {6, 2, 9, 4} です。重複した 2 は追加される際にまとめられます。次に nums2 を順に見て、各値がセットにあるかを定数時間で確認します。最初の 4 はセットにあるので、答えに追加します。2つ目の 4 は追加してはいけないため、一致した値はその時点でセットから削除します。1 はセットになく、6 はあるので、結果は [4, 6] になります。

一致したときに削除することで、各値が一度だけ含まれるようになります。最初に一致した後はその値がセットからなくなるため、nums2 内の後続の重複値は見つかりません。追加される値はすべて両方の配列に含まれており、共通する値はすべて、nums2 内で最初に現れたときに追加されます。

セットの構築と走査にかかる時間は、平均で O(n + m) です。答えは nums2 の順に出力されるので、最後にソートします。答えには k ≤ min(n, m) 個の値が含まれるため、ソートには O(k log k) かかります。Cには組み込みのセットがないため、Cのコードでは value + 10^5 をインデックスにするフラグ配列を使用します。値の範囲が限られているため、これが可能です。