アルゴリズム：指定された2つの配列から欠落している要素を見つけ、2番目の配列は重複しています

Question

指定された2つの配列から欠落している要素を見つけ出し、2番目の配列は重複しています。

例： アレイ1：[1,2,3,4,5,6,7] アレイ2：[1,3,4,5,6,7]

Iは使用読んハッシュマップやその他の複雑なアプローチがありますが、私は最良の解決策は次のように考えています：

1）sum1とsum2を持つように、array1とarray2のすべての要素を別々に追加すると、答えは| sum2 - sum1 |

2）xor1とxor2を持つように、array1とarray2のすべての要素を別々にXORします。ここで、xor1は常に完全配列からです。配列

は私が修正アムソートされていません：欠落している要素は

編集（XORアプリケーションhttp://www.codeproject.com/Articles/2983/XOR-tricks-for-RAID-data-protectionから）XOR2のXOR XOR1になりますか？

Answer 1

はい、配列に整数が含まれていると仮定すると、正しいアルゴリズムです。この証拠は、簡単には、x^x=0if and only ifx=xという事実に従います。配列に重複が含まれている場合でも機能します。

証明スケッチ。 Aをn個の整数の配列とし、Bを1つの要素が削除されたAのコピーとします。 xorA := A[0]^A[1]^...^A[n-1]とxorB := B[0]^...^B[n-2]を定義します。欠品以外の各要素はでも回と表示されますので、xorA^xorBは表示される欠損要素と同じになります奇数回数---その他はすべてx^x=0のためキャンセルします。

Answer 2

非常に大きな数値の場合、最初の答えで整数オーバーフローが発生することがあります。

第2のオプションは、すべての面で優れています。さらに、第1のアレイは、第1のアレイを含むアレイである必要はない。最初の配列の先頭から2番目の配列の最後の要素まで排他的論理和を開始することができます。両方の配列を結合したユニークな要素になります。 O（n）の複雑さにはコストがかかります。