[LeetCode] 136. Single Number

136. Single Number

Easy

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.

 

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

---

문제 해설

문제 접근

1. 숫자들이 들어있는 리스트의 크기는 N^2 시간복잡도 알고리즘을 사용해도 문제없어 보인다. 
2. 숫자의 값 크기도 신경쓰지 않아도 될 것 같다. 
3. 각 숫자는 한번 나타는 숫자 이외에는 두번씩 나온다. 

풀이

1. Set 을 사용하여 숫자를 집어 넣는다.
2. 만일 숫자가 존재하면 제거한다.
3. 마지막에 남은 숫자를 pop 하여 리턴한다.

소스 코드

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