[LeetCode] Single Number (Map()을 활용해 풀기)

문제 : 

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.

 

주어진 integer 배열 nums에는 단 하나를 제외하고 모든 숫자가 2번씩 등장한다. 한 번만 나타나는 숫자를 찾아라.

반드시 선형 복잡도와 추가 공간 사용없이 문제를 해결해야한다. 

 

* 선형복잡도(linear runtime complexity) 

: 입력값과 시간이 같은 비율로 증가 O(n)

풀이 : 

/**
 * @param {number[]} nums
 * @return {number}
 */
const singleNumber = function(nums) {
    const numsMap = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        numsMap.set(nums[i],numsMap.get(nums[i]) + 1 || 1);
    }
    
    for (let [key,value] of numsMap) {
        if (value < 2) {
            return key
        }
    }
    
};

Runtime: 51 ms

Memory Usage: 48.5 MB

 

풀이 아이디어는 예전에 프로그래머스에서 풀었던 [신고결과 받기]에서 얻었다. 

numsMap에 숫자별로 카운트를 set 하는 형식으로 

   numsMap.set(nums[i],numsMap.get(nums[i]) + 1 || 1);

numsMap에 해당 숫자가 있다면 +1, 없다면 1을 set 해준다.

모든 값을 다 담고 나면 for문을 돌려 값이 1개 뿐인 key를 return 

우수답안 풀이 (XOR 활용)

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
     let result = 0; 
    for(let num of nums){ 
        result ^= num; 
    } 
    return result;    
};

다른 답들을 찾다가 블로그에 'XOR 연산'을 활용하는 문제라는 말이 많이 보였는데 

XOR연산으로, 대응되는 비트가 서로 같으면 0을 다르면 1을 반환한다.