[268][简单] 缺失数字

题目描述

268. 缺失数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1]
输出: 2

示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明:

• 你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

解题思路

数学法

由于题目限定了只缺失了一个数, 因此求0, 1, 2, ..., n的总和, 减去数组所有数字之和, 差值就是缺失的数字.

位运算

Leetcode官方题解: 缺失数字

由于异或运算满足结合律, 并且对一个数进行两次完全相同的异或运算会得到原来的数, 因此我们可以通过异或运算找到缺失的数字.

我们将0, 1, 2, ..., n这$n+1$个数字进行异或, 然后在对数组中的每个数字进行异或, 在数组中出现过的数字, 都可以找到相同的数字进行异或, 化为0, 在数组中没有出现过的数字, 就会被留下.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        missing = 0
        for i in range(n):
            missing ^= i ^ nums[i]
        missing ^= n
        return missing