LeetCode 136 - Single Number ( JavaScript )

 

안녕하세요 besforyou입니다

 

이번 글은 LeetCode 136 - Single Number ( JavaScript ) 문제풀이입니다

 

---

문제 풀이

 

1. 시간복잡도 O(N) , 공간복잡도 O(N) 버전

 

맵을 구현하여 숫자가 배열에 몇 개 있는지 모두 센 뒤, 한 개만 있는 숫자를 반환합니다.

 

var singleNumber = function(nums) {
    
    const map = {};
    for (const n of nums) {
        if (map[n] == null){ 
            map[n] = 0;
        }
        else
            map[n]++;
    }
    
    for (const n of nums) 
        if (map[n] == 0) return n;
};

 

2. 시간복잡도 O(N) , 공간복잡도 O(1) 버전

 

XOR를 이용합니다. 같은 숫자가 두 번 곱해지면 비트가 0이 되는 것을 이용한 풀이입니다.

 

var singleNumber = function(nums) {
    let num = nums[0];
    
    for (let i = 1 ; i < nums.length ; i++) num ^= nums[i];
    
    return num;
};