리트코드 268번

나의 1차 풀이

var missingNumber = function(nums) {
    let arr = nums.sort((a,b) => a-b);
    if (arr[0] !== 0) return 0;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] + 1 !== arr[i+1]) {
            return arr[i]+1;
        }
    }
};

시간 복잡도가 O(nlongn)이고, 공간복잡도도 O(n)이다.
리트코드 추가 질문에서 공간복잡도 O(1)에 시간 복잡도 O(n)으로 구현해보라고 한다.

나의 2차 풀이

var missingNumber = function(nums) {
    let sum = 0;
    for (let i = 0; i <= nums.length; i++) {
        sum+=i;
    }
    for (let x of nums) {
        sum-=x;
    }
    return sum;
};

배열의 길이를 이용해 전체 원소의 합을 구하고, nums를 순회하면서 sum에서 원소 값을 빼면 나오는 sum의 값이 등장하지 않은 원소다. 저번에 비슷한 문제를 풀었을 때 전체 합을 이용하는 방법이 있었던 것이 떠올랐다. 실행시간이 50% 감소했다.

좋은 웹페이지 즐겨찾기