(Leetcode) 268 - Missing Number
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/missing-number/description/
Bit Manipulation 문제에 속해있는데 Array 문제로 봐야하지 않나 싶다.
내가 작성한 풀이
public int missingNumber(int[] nums) {
int[] counts = new int[nums.length + 1];
for(int num : nums) {
counts[num] = 1;
}
for(int i = 0; i < counts.length; i ++){
if(counts[i] == 0) {
return i;
}
}
return -1;
}
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다.
등차수열로 풀기
예전에 1부터 100까지 더해보라고 하면 개발자들은 반복문부터 돌린다는 이야기를 들어본 적이 있다. 당시의 발표자는 ‘등차수열의 합’에 대한 언급을 하였다.
이 풀이에서는 등차수열의 합을 이용해서 모든 수가 있을 때의 예상 합(max)을 계산한다. array를 돌면서 sum을 계산한다. 그리고 max와 sum의 차를 구하면 빠진 숫자가 무엇인지를 알 수 있다.
public int missingNumber(int[] arr) {
int sum = 0;
int max = (arr.length * (arr.length + 1)) / 2;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
return max - sum;
}
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)이다.