[LeetCode] Single Number

https://leetcode.com/problems/single-number/description/?envType=study-plan-v2&envId=leetcode-75

 

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.

---

 

숫자가 들어 있는 배열이 주어지고, 그 안에서 딱 한번만 등장하는 숫자를 찾는 문제.

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    const numMap = new Map();
    for(const num of nums){
        numMap.set(num, numMap.get(num) ? 2 : 1);
    }

    for(const [num, count] of numMap){
        if(count == 1){
            return num;
        }
    }

};

 

단순히 for문 한 번 돌려서 Map에 카운트 수 넣고 그 map에서 count가 1인 숫자가 나오면 바로 리턴한다.

 

이걸로도 나쁘지는 않지만... 비트연산자 중 XOR 연산자를 사용하면 좀 더 간편하게 할 수 있다.

var singleNumber = function(nums) {
    let result = 0;
    for(const num of nums){
        result ^= num;
    }
    return result;
};

 

XOR 연산자는 비트가 다르면 1을, 같으면 0로 비교되는 위치의 비트를 바꿔주는 연산자다.

왜 이게 되냐면, 테스트케이스 중 [4, 1, 2, 1, 2]로 예를 들어 보자.

 

num	result ^= num	result
4	0 ^ 4	0000 ^ 0100 = 0100 = 4
1	4 ^ 1	0100 ^ 0001 = 0101 = 5
2	5 ^ 2	0101 ^ 0010 = 0111 = 7
1	7 ^ 1	0111 ^ 0001 = 0110 = 6
2	6 ^ 2	0110 ^ 0010 = 0100 = 4

 

위 표에서 나온 것처럼, XOR은 현재 순서의 숫자의 비트가 겹치는 만큼 전환해 준다.

즉, 두 번 나온 숫자들은 동일한 위치의 비트가 2번 바뀌므로, 다 0000으로 상쇄된다.

결국 0에서 시작한 result는 결국 한 번만 나온 숫자의 이진수와 같은 비트를 갖게 된다. ~.~ 

 

끝!