[리트코드] Single Number

박형진·2021년 12월 22일
0

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


1. 전체코드

1. XOR 풀이

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

2. 사전자료형 풀이

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        d = defaultdict(int)
        for num in nums:
            d[num] += 1
        for i in d:
            if d[i] == 1:
                return i

2. 후기

first = 0
a = first ^ 70  #출력 70
b = a ^ 34      #출력 100
c = b ^ 70      #출력 34
d = c ^ 20      #출력 54
e = d ^ 34      #출력 20

두 번의 XOR 연산을 사용한 70과 34는 초기화 되었지만, 한 번의 XOR 연산만을 한 20은 값이 그대로 보존된다. 중요한 점은 같은 수가 등장하는 순서는 상관이 없다는 것이다.

예를들어, 13^512^7^512^9^7^13 같은 복잡한 연산도 쉽게 답을 알 수 있다.
두 번 사용된 13, 512, 7은 소멸되고 9만 보존된다.

profile
안녕하세요!

0개의 댓글