[leetcode][260] Single Number III

문제 : https://leetcode.com/problems/single-number-iii/

---

 

2개의 요소는 단 하나만 존재하고 이 외의 요소들은 두 개씩 있는 nums 배열이 주어진다.

하나만 존재하는 2개 요소를 찾아라. (요소의 순서는 상관없다. 선형 시간복잡도로 구현하라.)

---

nums 배열을 탐색하면서 모든 요소들의 XOR 연산 결과를 sum 변수에 저장한다.

XOR 연산은 홀수번 나온 비트는 1, 짝수번(0포함) 나온 비트는 0으로 세팅된다.

즉, XOR연산 결과는 1개만 존재하는 수의 XOR 결과와 같다. (나머지 수들은 2번 XOR 연산되므로 A XOR A = 0. 이 되므로 무시해도 된다.)

하나만 존재하는 요소를 각각 A, B라고 했을 때, A는 B와 같지 않으므로 A XOR B = 0 이 될 수 없다.

따라서 sum은 0이 될 수 없다.

 

sum에서 뒤에서 처음으로 나오는 1 비트를 구한다.(let, lastSettedBit) (참고)

이제 A와 B 중 이 비트를 가지는 수를 구할것이다.

A와 B의 XOR 결과 중 1이 되는 비트를 가지고 온 것이기 때문에 A, B 중 하나의 수만 해당 비트를 가진다.

lastSettedBit를 가지는 수를 구하는 방법은 nums 배열을 모두 탐색하면서 lastSettedBit와 nums[i]를 AND 연산한 결과가 lastSettedBit와 같은지 확인한다. 만약 lastSettedBit와 같다면 nums[i]는 lastSettedBit를 가지는 정답 수 중 하나가 될 가능성이 있다는 뜻이다. 그러나 정답이 아닌 두번씩 나오는 요소도 lastSettedBit를 가질 수 있기 때문에 이를 걸러낼 필요가있다.

따라서 위에서 언급한 조건을 가지는 수들을 모두 XOR 연산한다. 두 번 나타나는 수는 XOR 결과로 없어지므로 순수한 정답 중 하나인 수만 구할 수 있다. 구한 수를 A라 한다면 나머지 정답 수 하나(let, B)는 sum XOR A가 된다. (A XOR B = ans. 이기 때문)

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/260.%20Single%20Number%20III.cpp

---

참고 : youtu.be/YvKENIOEaYE

위 영상을 보고 풀었습니다. :+1: