2021년 3월 LeetCoding Challenge — 3일차: 숫자 누락

문제 설명

범위 [0, n]에서 n개의 고유한 숫자를 포함하는 배열 nums가 주어지면 범위에서 배열에서 누락된 유일한 숫자를 반환합니다.

예 1:

**Input:** nums = [3,0,1]
**Output:** 2
**Explanation:** n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

예 2:

**Input:** nums = [0,1]
**Output:** 2
**Explanation:** n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

예 3:

**Input:** nums = [9,6,4,2,3,5,7,0,1]
**Output:** 8
**Explanation:** n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

예 4:

**Input:** nums = [0]
**Output:** 1
**Explanation:** n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.

제약:

n == nums.length

1 <= n <= 104

0 <= nums[i] <= n

숫자의 모든 숫자는 고유합니다.

해결책

이 문제는 여러 접근 방식으로 해결할 수 있습니다. 배열에서 누락된 숫자를 찾아야 합니다.

접근법 1 — 정렬: 이 문제를 해결하기 위해 정렬을 사용할 수 있습니다. 배열이 정렬되면 인접한 요소를 확인하고 차이점을 확인할 수 있습니다. 차이가 1보다 크면 누락된 숫자, 즉 i번째 인덱스와 (i+1)번째 인덱스에서 이 두 숫자 사이의 숫자를 찾은 것입니다.

시간 복잡도: O(nlogn), 배열을 정렬하는데 필요한 시간

공간 복잡도: O(1), 추가 공간이 사용되지 않음

접근법 2 — HashSet: HashSet을 사용하여 이 문제를 해결할 수 있습니다. HashSet에 숫자를 저장하고 두 번째 반복에서 숫자가 없으면 0에서 n까지 확인한 다음 반환합니다.

시간 복잡도: O(n)

공간 복잡도: O(n)

여기에서 코드를 찾을 수 있습니다.