[Leetcode] 136. Single Number 문제 풀이

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

Single Number - LeetCode

 

문제 내용

배열에 2개씩 숫자쌍이 있는데 혼자만 있는 숫자 찾기

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

 

문제 풀이

hash로 count 하는 단순한 방법은 공간 복잡도가 O(n) 만큼 든다.

공간 복잡도가 O(1) 만큼 하는 방법이 있다.

xor 연산자를 활용하는 방법이다.

 

xor 은 같으면 0이 되는 연산이다.

x ^ y ^ x 를 연산했을 때 

(x ^ x) ^ y 와 같은 결과를 얻을 수 있다.

그래서 순차적으로 xor 연산만 해주면 된다.

 

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (auto num : nums)
            ans = ans ^ num;
        return ans;
    }
};