Written by Lee Jongseo
on May 12, 2021

Alogrithm[1]:⭐ - Single Number

Q. Leetcode: 136. Single Number

방법 1. dictionary 자료형 이용

리스트를 순회하여 key는 num, value는 count를 가지는 dictionary를 만든다.
dictionary를 순회하여 value가 1인 key값을 찾아 반환한다.

dict.get()

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        table = {}
        for num in nums:
            table[num] = table.get(num, 0) + 1
        for key, value in table.items():
            if value == 1:
                return key

defaultdict

from collections import defaultdict
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        table = defaultdict(int)
        for num in nums:
            table[num] += 1
        for key, value in table.items():
            if value == 1:
                return key

방법 2. XOR operator 이용

^ : xor operator

Example

print(3 ^ 3) # 0
print(0 ^ 3) # 3

동일한 number를 연산하는 경우 0 이 나오고 0과 연산할 경우 0이 아닌 operand가 나온다.

이를 이용해 다음과 같은 알고리즘이 가능하다.

값이 0인 변수를 선언한다.
리스트를 순회하여 0과 리스트 요소와 ^ 연산을 수행한다.

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

👈 👉 Top