丢失的数字

发表于 | 分类于 |
字数统计: 707 字 | 阅读时长 ≈ 2 分钟

题目描述：给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

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

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

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

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

位运算

  • 因为输入的数组长度为len，数组下标为[0…len-1]，数组中可能出现的数字是0到len
  • 所以设置ans的初始值为len，即可和数组中可能出现的数字len进行异或运算后为0
  • 然后循环遍历整个数组，ans每次和数组的下标及数组中的数字进行异或运算，最终ans的结果就是缺失的数字

输入：nums = [3,0,1]，则ans = nums.length = 3
输出：ans = ans ^ 0 ^ nums[0] ^ 1 ^ nums[1] ^ 2 ^ nums[2]
= 3 ^ 0 ^ 3 ^ 1 ^ 0 ^ 2 ^ 1
= 0 ^ 0 ^ 1 ^ 1 ^ 2 ^ 3 ^ 3（异或运算满足交换律）
= 0 ^ 0 ^ 2 ^ 0 （数字自身异或为0）
= 2 （任何数字和0进行异或运算结果不变）

1
2
3
4
5
6
7
8
var missingNumber = function(nums) {
    let xor = nums.length
    for(let i = 0; i < nums.length; i++) {
        xor ^= i
        xor ^= nums[i]
    }
    return xor
};

复杂度分析

  • 时间复杂度：O(n)。这里假设异或运算的时间复杂度是常数的，总共会进行 O(n) 次异或运算，因此总的时间复杂度为 O(n)。
  • 空间复杂度：O(1)。算法中只用到了 O(1) 的额外空间，用来存储答案。

数学

用0-n的总和减去数组总和

  • 0 - n 的总和用等差数列:（首数+尾数）* 项数 / 2 来求
1
2
3
4
5
6
7
8
var missingNumber = function(nums) {
    let len = nums.length
    let sum = (1 + len) / 2 * len
    for(let i = 0; i < len; i++) {
        sum -= nums[i]
    }
    return sum
};

复杂度分析

  • 时间复杂度：O(n)。循环减去数组的所有数字的时间复杂度为 O(n)，高斯求和公式的时间复杂度为 O(1)，因此总的时间复杂度为 O(n)
  • 空间复杂度：O(1)。算法中只用到了 O(1) 的额外空间，用来存储答案