추가 스토리지 없이 O(n) 시간에 SingleNumber 솔루션

문제 설명

비어 있지 않은 정수 배열이 주어지면 모든 요소는 하나를 제외하고 두 번 나타납니다. 그 하나를 찾으십시오. 참고: 알고리즘은 선형 런타임 복잡성을 가져야 합니다. 추가 메모리 없이 구현할 수 있습니까?

사고 과정

나의 초기 결론은 아니오, 당신은 할 수 없다는 것이었습니다. 배열에 가능한 숫자의 범위가 없고 배열이 아직 정렬되지 않았기 때문에 개체를 사용하여 개수를 저장하는 경우 선형 시간으로 해결할 수 있지만 추가 저장 또는 정렬이 필요하면 O(n log n ).

하지만 XOR(^)을 잊어버렸습니다. 비트를 가지고 놀지 않는 사람들을 위해 배타적이거나 두 개의 이진수를 취하고 한 숫자는 비트가 뒤집히고 다른 숫자는 그렇지 않은 쌍의 경우 결과 숫자가 비트가 뒤집힙니다.

  01101
^ 10110
= 11011

따라서 숫자가 있고 0으로 XOR하면 숫자를 얻습니다. 숫자가 있고 그 자체로 XOR하면 0이 됩니다.

이제 도움이 됩니다. 하지만 왜 이 문제에 대해 XOR에 신경을 쓰겠습니까?

예제를 실행해 보겠습니다.

input:  [4,1,1,2,2,4,5,1,2,1,2]
4^1=5
5^1=4
4^2=6
6^2=4
4^4=0
0^5=5
5^1=4
4^2=6
6^1=7
7^2=5

설명/해결책

두 번 나타나는 모든 값은 결국 자체적으로 취소되기 때문에 파트너가 없는 하나의 고독한 요소만 남게 됩니다. 추가 저장 공간이 필요하지 않습니다. 선형 시간.

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