LeetCode 冥想：缺失的数字

题目描述：给定一个包含 0 到 n 范围内的 n 个不同数字的数组 nums，找出该范围内数组中唯一缺失的数字。

示例：

输入：nums = [3, 0, 1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有数字都在范围 [0, 3] 内。2 是范围内缺失的数字，因为它没有出现在 nums 中。

登录后复制

输入：nums = [0, 1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有数字都在范围 [0, 2] 内。2 是范围内缺失的数字，因为它没有出现在 nums 中。

登录后复制

输入：nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有数字都在范围 [0, 9] 内。8 是范围内缺失的数字，因为它没有出现在 nums 中。

登录后复制

说明：所有 nums 中的数字都是唯一的。

一种简单的解法是计算范围的总和，然后减去给定数组的总和。剩余的值就是缺失的数字。可以使用 reduce 方法来计算数组的总和：

function missingNumber(nums) {
  const n = nums.length;
  const expectedSum = (n * (n + 1)) / 2;
  const actualSum = nums.reduce((sum, num) => sum + num, 0);
  return expectedSum - actualSum;
}

登录后复制

该方法的时间和空间复杂度均为 O(n)。

为了提高效率，可以使用位运算（异或）。 xor 运算的特性是：相同数字异或结果为 0，任何数字与 0 异或结果为自身。

我们可以将数组中每个数字与其索引进行异或运算。由于所有数字都是唯一的，最终所有数字都会抵消，只剩下缺失的数字。为了处理缺失数字等于数组长度的情况，我们将结果初始化为数组长度：

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

登录后复制

该方法的时间复杂度为 O(n)，空间复杂度为 O(1)。

时间和空间复杂度分析：

时间复杂度：O(n)，因为我们需要遍历数组一次。 空间复杂度：O(1)，因为我们只使用了常数个额外的变量。

接下来，我们将继续探讨系列中的下一个问题。祝您编码愉快！

以上就是LeetCode 冥想：缺失的数字的详细内容，更多请关注其它相关文章！

Tags： 数字缺失