単数

問題声明
整数の空でない配列を指定すると、すべての要素は1以外の2回表示されます.そのシングルを見つけてください.注意:アルゴリズムは、線形実行時複雑さを持つ必要があります.余分なメモリなしでそれを実装できますか?

思考過程
私の最初の結論は、いいえ、あなたはできませんでした.配列の可能な数の範囲がなく、配列が既にソートされていないので、カウントを格納するためにオブジェクトを使用した場合、線形時間で解決することができますが、余分なストレージまたはソートがO(N log N)である必要があります.
しかし、私はxor(^)を忘れました.ビットでは、排他的な、または2つのバイナリ番号を取り、1つの番号のビットを反転し、他のしないペアでは、結果の番号は、ビットを反転してください.

  01101
^ 10110
= 11011

それで、あなたが数と0によってそれをXORするならば、あなたは数を得ます.あなたが数とXORをそれ自身で持っているならば、あなたは0を得ます.
さて、それは役に立つですが、なぜあなたはこの問題のためにXORを気にするでしょうか?
例を通して走りましょう.

const input = [4,1,1,2,2,4,5,1,2,1,2]
let num = input[0];

for (let i = 1; i < input.length; i++) {
    num ^= input[i];
    console.log(num);
}

/*
5
4
6
4
0
5
4
6
7
5
*/

説明解
二度表示される値のすべてが最終的に自分自身をキャンセルするので、あなたはパートナーがいないその1つの単体要素を残しています.余分なストレージは必要ありません.線形時間.

  100 // 4
^ 001 // 1
= 101 // 5
^ 001 // 1
= 100 // 4
^ 010 // 2
= 110 // 6
^ 010 // 2
= 100 // 4
^ 100 // 4
= 000 // 0
^ 101 // 5
= 101 // 5
^ 001 // 1
= 100 // 4
^ 010 // 2
= 110 // 6
^ 001 // 1
= 111 // 7
^ 010 // 2
= 101 // 5

数の配列で動作しているので、forループの代わりに、Arrayメソッドを使用してタスクを実行できます.

function singleNumber(nums) {
    return nums.reduce((a, b) => a ^ b)
}

LeetCodeからの問題