리트코드 268번
4824 단어 JavaScript알고리즘코딩 테스트JavaScript
나의 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% 감소했다.
Author And Source
이 문제에 관하여(리트코드 268번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@htogether7/리트코드-268번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)