리트코드 - 136. Single Number

https://leetcode.com/problems/single-number/description/

Single Number - LeetCode

두 숫자의 Xor는 비트의 차이를 1로, 같은 비트를 0으로 나타낸다.
따라서 이를 사용하면 같은 숫자는 같은 비트를 가지므로 1 ^ 1 == 0이 된다.
따라서 동일한 요소는 모두 0으로 평가되기 때문에 마지막에 남는 비트를 확인하면 항상 단일 요소를 얻게 된다.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        count = 0

        for num in nums:  # O(n)
            count ^= num  # O(1) 최악의 경우 (너무 큰 숫자) O(n)

        return count

 

nums 리스트의 길이만큼 순회하므로 시간복잡도는 O(n)이다.

정수 값으로 비트연산을 통해 단일 요소 여부를 저장하므로, O(1)의 공간복잡도를 갖는다, 단 너무 큰 숫자의 비트 연산을 수행할 경우에는 숫자의 크기, O(n)의 공간복잡도를 최악으로 가진다.