LeetCode 冥想：缺少的數字

我們先來描述這個問題：

給定一個陣列 nums，其中包含 [0, n] 範圍內的 n 個不同數字，傳回 該範圍內數組中唯一缺少的數字。

例如：

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.

也指出所有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🎜> O(n)

使用此解決方案，我們為該範圍建立一個陣列。

我們可以使用位元操作來獲得更（

儲存方面
）高效的解決方案。

事實上，我們可以使用 XOR 運算來幫助我們實現這一點。

要記住，如果兩個位元都不同，則 XOR 結果為 1，即其中一個為 0，另一個為 1。

當我們將一個數字與其自身進行異或時，結果將是 0，因為所有位元都是相同的。

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

例如，二進位的 3 是 11，當我們執行 11 ^ 11 時，結果是 0：

換句話說，

數字與自身的異或運算將得到 0

。

如果我們將數組中的每個數字與索引進行異或，最終所有數字都會抵消（結果為 0），只留下缺少的數字。

你可能會認為並不是所有的數字都在它們的索引處，例如如果 nums 是 [3, 0, 1]，很明顯 3 甚至沒有可以與之關聯的「索引 3」！

let result = nums.length;

為此，我們可以先將結果初始化為 nums.length。現在，即使缺少的數字等於 nums.length，我們也會處理這種邊緣情況。

此外，
XOR 是可交換和結合的

，因此數字出現在哪個索引處並不重要（或者沒有一個，如上面的示例） - 它們最終會抵消。

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

現在，透過 for 循環，我們可以使用位元異或賦值運算子進行異或：

並且，最終的結果是缺少的數字。解決方案總體如下所示：

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(n)$\mathrm{O}()$1)O(1)

---

O(1) 因為我們沒有任何額外的儲存需求，這些需求會隨著輸入大小的增加而增加。 接下來，我們來看看整個系列的最後一個問題，兩個整數的和。在那之前，祝您編碼愉快。

以上是LeetCode 冥想：缺少的數字的詳細內容。更多資訊請關注PHP中文網其他相關文章！