136. Single Number

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.

 

Solution

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

• xor 연산을 활용한다.
• 같은 값을 xor연산을 하면 0이 되므로, nums의 모든 요소를 xor 하면 중복되지 않고 하나의 값만 존재하는 수가 남는다.