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) 使用此解决方案，我们为该范围创建一个数组。

我们可以使用位操作获得更（存储方面）高效的解决方案。
事实上，我们可以使用 XOR 运算来帮助我们实现这一点。

要记住，如果两个位都不同，则 XOR 结果为 1，即其中一个为 0，另一个为 1。
当我们将一个数字与其自身进行异或时，结果将是 0，因为所有位都是相同的。

例如，二进制的 3 是 11，当我们执行 11 ^ 11 时，结果是 0：

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

换句话说，数字与自身的异或运算将得到 0。

如果我们将数组中的每个数字与索引进行异或，最终所有数字都会抵消（结果为 0），只留下缺失的数字。

你可能会认为并不是所有的数字都在它们的索引处，例如如果 nums 是 [3, 0, 1]，很明显 3 甚至没有可以与之关联的“索引 3”！

为此，我们可以首先将结果初始化为 nums.length。现在，即使缺失的数字等于 nums.length，我们也会处理这种边缘情况。

let result = nums.length;

此外，XOR 是可交换和结合的，因此数字出现在哪个索引处并不重要（或者没有一个，如上面的示例） - 它们最终会抵消。

现在，通过 for 循环，我们可以使用按位异或赋值运算符进行异或：

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) 因为我们没有任何额外的存储需求，这些需求会随着输入大小的增加而增加。

---

接下来，我们来看看整个系列的最后一个问题，两个整数的和。在那之前，祝您编码愉快。

以上是LeetCode 冥想：缺失的数字的详细内容。更多信息请关注PHP中文网其他相关文章！