缺失数字

发表于 分类于 阅读次数：

缺失数字（难度：简单）

3

方法一：数学方法

用序列[0,1,...,n]的和减去给定的nums的和，可得到缺失的数字。

复杂度

时间复杂度：O(n)。

空间复杂度：O(1)。

代码
1
2
3
4
5
6
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        sum1 = sum(range(0,len(nums)+1)) # 0,1,...,n 序列的和(或用高斯求和公式)
        sum2 = sum(nums)

        return sum1 - sum2
1

高斯求和有溢出风险

方法二：位运算（异或运算）

先得到[0,1,...,n]的异或值，再将结果对数组nums中的每一个数进行一次异或运算，最终的异或结果即为这个缺失的数字。

在编写代码时，由于[0,1,...,n]恰好是这个数组的下标加上 n，因此可以用一次循环完成所有的异或运算。

复杂度

时间复杂度：O(n)。假设异或运算的时间复杂度是常数的。

空间复杂度：O(1)。

代码
1
2
3
4
5
6
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        res = len(nums) # 一开始初始化为n
        for i in range(0,len(nums)):
            res ^=  i ^ nums[i]
        return res
2