LeetCode 명상: 누락된 숫자

이 문제에 대한 설명부터 시작하겠습니다.

[0, n] 범위의 고유 숫자 n개를 포함하는 nums 배열이 있는 경우 배열에서 누락된 범위의 유일한 숫자를 반환합니다.

예:

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.

또는:

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.

또는:

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.

또한 모든 숫자는 고유하다고 명시되어 있습니다.

---

이 문제를 해결하는 쉬운 방법 중 하나는 범위의 총합을 구한 다음 주어진 배열의 합을 빼는 것입니다. 남은 것은 누락된 숫자가 될 것입니다.

reduce를 사용하여 다음과 같이 숫자의 합을 계산할 수 있습니다.

function missingNumber(nums: number[]): number {
  return Array.from({ 
    length: nums.length + 1 
  }, (_, idx) => idx).reduce((acc, item) => acc + item, 0) 
  - nums.reduce((acc, item) => acc + item, 0);
}

먼저 0부터 nums.length 1까지의 값을 갖는 배열을 생성하고 그 합을 구한 다음, 그 값에서 nums의 합을 뺍니다.

그러나 시간과 공간의 복잡성은 $O(n)$O(n) 이 솔루션을 사용하여 범위에 대한 배열을 생성합니다.

비트 조작을 사용하면 보다 효율적인(저장소) 솔루션을 얻을 수 있습니다.
실제로 XOR 연산을 사용하면 도움이 될 수 있습니다.

두 비트가 서로 다른 경우 XOR의 결과는 1입니다. 즉, 둘 중 하나는 0이고 다른 하나는 1입니다.
숫자 자체를 XOR하면 모든 비트가 동일하므로 결과는 0이 됩니다.

예를 들어 이진수 3은 11이고 11 ^ 11을 수행하면 결과는 0입니다.

const n = 3;
const result = n ^ n; // 0

즉, 숫자 자신과 XOR 연산을 수행하면 0이 됩니다.

인덱스가 있는 배열의 각 숫자에 대해 XOR을 수행하면 결국 모든 숫자가 취소되고(결과는 0이 됨) 누락된 숫자만 남게 됩니다.

모든 숫자가 해당 인덱스에 있는 것은 아니라고 생각할 수도 있습니다. 예를 들어 nums가 [3, 0, 1]인 경우 3에는 이와 연결할 수 있는 "인덱스 3"조차 없다는 것이 명백합니다!

이를 위해 결과를 nums.length로 초기화하는 것부터 시작할 수 있습니다. 이제 누락된 숫자가 nums.length와 같더라도 해당 극단적인 경우를 처리합니다.

let result = nums.length;

또한 XOR은 교환적이고 결합적입니다. 따라서 어떤 인덱스에 숫자가 나타나는지는 중요하지 않습니다(또는 위의 예와 같이 숫자가 없는 경우). 결국에는 상쇄됩니다.

이제 for 루프에서 비트별 XOR 할당 연산자를 사용하여 XOR을 수행할 수 있습니다.

for (let i = 0; i < nums.length; i++) {
  result ^= i ^ nums[i];
}

그리고 최종 결과는 숫자가 누락된 것입니다. 전체적인 솔루션은 다음과 같습니다.

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.

시간과 공간의 복잡성

다시 시간복잡도가 발생합니다 $O(n)$O(n) 배열의 각 숫자를 반복하지만 공간 복잡도는 다음과 같습니다. $O(1)$O(1) 입력 크기가 증가함에 따라 늘어나는 추가 저장 공간이 필요하지 않기 때문입니다.

---

다음으로는 전체 시리즈의 마지막 문제인 Sum of Two Integers를 살펴보겠습니다. 그때까지 즐거운 코딩하세요.

위 내용은 LeetCode 명상: 누락된 숫자의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!