문제설명

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

정수 배열에서 하나의 요소만 제외하고 다른 요소는 모두 두 번씩 나온다고 한다. 그걸 찾아야 되는데 시간복잡도는 O(n), 공간복잡도는 O(1)로 찾으라고 한다.

내 풀이

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        length = len(nums)
        for i in range(0, length, 2):
            if i + 1 >= length or nums[i] != nums[i + 1]:
                return nums[i]

일단 정렬을 해서 0번째 인덱스부터 두 칸씩 뛰며 다음 요소와 비교하게 했다. 정답은 맞지만 sort()를 쓰는 것은 O(nlogn)이므로 요구사항을 만족시켰다고 보기는 힘들 것 같다.

정답(?)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        answer = 0
        for num in nums:
            answer = answer ^ num
        return answer

배타적 논리합(XOR)을 사용하는 방법이다...
배타적 논리합은 1의 개수가 홀수일 때 1의 값을 가진다. 즉, 둘 다 0 또는 1이면 0이고 그 외에는 1이라는 소리다.

예를 들어, 4를 이진수로 표현하면 100이고, 2를 이진수로 표현하면 010이다.
위와 같이 표현이 된다.

[4, 1, 2, 1, 2] 라고 할 때, answer는 4 -> 5 -> 7 -> 6 -> 4가 된다. 이렇게 될 수 있는 이유는 이전에 배타적 논리합을 했던 수를 다시 배타적 논리합을 하면 상쇄되어 0이 되기 때문이다. 이렇게 해서 Single인 친구를 찾을 수 있다...! 환상의 풀이가 따로없다...