136. Single Number

모든 수는 두 번씩 나타난다, 한 개만 빼고.
그 하나의 수를 찾아라.

Solution

숫자를 차레대로 set에 저장한다. 만약 이미 set에 있다면 저장 대신 삭제한다.

최대 등장 횟수가 두 번이므로 가능한 풀이다.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        s = set()
        for i in nums:
            if i in s: s.remove(i)
            else: s.add(i)
        return s.pop()

시간 복잡도

모든 배열을 검사하므로 O(n)이다.