问题
一个无序数列存储了 0~n 这 n+1 个数字，去除一个。如何查找这个丢失的数字？
解法
求差
用未去除的数列和减去现在的数列和，即为缺失的数字。
1
2
def get_missing_num(nums):
return sum([x for x in range(len(nums) + 1)]) - sum(nums)
这种方法，其实遍历了2次。
可以使用等差数列求和的方法求前 n 项的和，以减少遍历的次数。
对于等差数列 \({a_1},{a_2},{a_3} \cdots {a_n}\)，其中
\[{a_n}={a_1}+(n-1) \times d\]等差数列的和：
\[{S_n}=n{a_1}+ \frac{n(n-1)}{2}d\]或
\[{S_n}=\frac{n({a_1}+{a_n})}{2}\]方法如下：
1
2
def get_missing_num(nums):
return int(len(nums) * (0 + len(nums) + 1) / 2) - sum(nums)
位运算
可以利用二进制的异或运算消掉没有去除的数字，那么首先要把每个数字都复制一个，再用异或消除。
参考：二进制的异或运算
1
2
3
4
5
6
from functools import reduce
def get_missing_num(nums):
tmp_nums = nums + [x for x in range(len(nums) + 1)]
return reduce(lambda x, y: x ^ y, tmp_nums)
上面的这种方法，也遍历了2次，可以优化为以下方法：
1
2
3
4
5
6
7
8
def get_missing_num(nums):
# 先初始化为有序数列中的首位，即 0
result = 0
for i in range(len(nums)):
# 将数列中的每位与有序数列中的每位(从 1 到 n)异或运算
result ^= (i + 1) ^ nums[i]
# 最终的结果即为缺失的数字
return result