[LeetCode] Single Number(JS)

문제

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?

입출력 예
Input: nums = [2,2,1]
Output: 1

접근

처음에 생각한 방법은 배열이나 객체를 새로 생성하는 방법이다.
1. 배열을 이용하는 방법은 nums의 요소를 새로운 배열에 push 하면서 이미 존재하는 요소를 push할 때에는 기존의 요소를 삭제하는 방법으로 결국 중복되지 않는 숫자만 마지막에 남게된다.
2. 객체를 생성하는 방법은 nums의 요소를 key 값으로 요소의 각 숫자를 value값으로 설정하여 value값이 1인 key값을 return 한다.

풀이

var singleNumber = function(nums) {
    /*
    // 1. 새로운 배열을 이용하여 하는 방법
    let arr = [];
    for(let i of nums){
        if(!arr.includes(i)){
            arr.push(i);
        }else{
        // splice는 인덱스를 이용하여 삭제하기 때문에 indexOf로 인덱스를 찾아 삭제하는 방법
            arr.splice(arr.indexOf(i),1)
        }
    }
    return arr[0];
    */
    
    // 2. 객체를 만들어 value값이 1인 경우를 return 하는 방법
    let obj = nums.reduce((acc,val)=>{
        if(!acc[val]){
            acc[val] = 1;
        }else{
            acc[val]++;
        }
        return acc;
    },{})
    
    for(let i in obj){
        if(obj[i] === 1){
            return i;
        }
        
    }
    

이렇게 작성했을 경우 첫번째 방법은 O(n*n)의 시간 복잡도를 예상할 수 있고, 두번째 객체를 이용한 방법은 O(n)의 시간복잡도를 예상할 수 있다.

추가

문제에서 memory를 늘리지 않는 방법도 권하고 있고 LeetCode에 추가적으로 solution이 있어 참고하여 코드를 작성하였다.

먼저 수학을 이용한 방법은
nums에서 중복의 요소를 제거하고 합을 구한 뒤 2를 곱한 값에서 원래의 배열인 nums의 합을 빼준다.
[a,a,b,b,c]라는 배열이 있을 때, 2∗(a+b+c)−(a+a+b+b+c)=c

그리고 memory를 추가하지 않는 방법으로는 비트를 이용한 방법이 있다.
ex)1⊕0 = 1, 1⊕1 = 0, 1⊕2 = 3
0을 따로 선언해주고 nums의 요소를 모두 XOR하여 마지막 값을 return한다.

a⊕b⊕a=(a⊕a)⊕b=0⊕b=b

var singleNumber = function(nums) {
    /*
    // 3. set과 합을 이용하는 방법
    return 2 * Array.from(new Set(nums)).reduce((acc,val) => acc+val) - nums.reduce((acc,val) => acc + val);
    */
    
    //4. bit를 통한 연산
    // 1 ^ 0 = 1, 1 ^ 1 = 0, 1 ^ 2 = 3
    let a = 0
    for(let i of nums){
        a ^= i
    }
    return a;
};

두 방법 모두 O(n)의 시간복잡도를 가지며 마지막 방법은 O(1)의 공간복잡도를 만족한다.

알고리즘을 풀면서 비트를 사용하여서 풀이한 것은 나에게는 거의 처음이라 생소했지만 이렇게도 풀 수 있구나 생각할 수 있었다.