[leetcode 136] Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

한 번만 등장한 원소 찾기

 

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

 

문제 풀이:

- follow up을 무시하고 map으로 풀면 쉽게 풀린다.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int answer;
        
        unordered_map<int, int> um;
        
        for(int i=0; i<nums.size(); i++){
            um[nums[i]]++;
        }
        
        for(auto i=um.begin(); i!=um.end(); i++){
            if(i->second == 1){
                answer = i->first;
                break;
            }
        }
        
        return answer;
    }
    
};

- 두 번째 방법 XOR사용하기

이런 걸 알아내는 사람들은 천재인가...자괴감이 든다.

XOR 연산: 입력값이 같으면 0, 입력값이 다르면 1이 된다.

 

A XOR A = 0

A XOR 0 = A

(A XOR A) XOR B = B

따라서 XOR을 사용하면 두 번 나온 애는 0이 되고 한 번 나온애만 그 값이 남는다.

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