Missing Number
你会得到一个包含 n 个互不相同整数的列表 nums，每个整数都在 0 到 n 之间。从 0 到 n 的范围内共有 n+1 个数，因此恰好有一个数不在列表中。返回这个缺失的数。
函数
- numsinteger-array
- n 个互不相同的整数，范围为 0 到 n，顺序任意
- 返回值integer
- 从 0 到 n 中没有出现在 nums 里的那个数字
约束条件
n == nums.length1 ≤ n ≤ 1040 ≤ nums[i] ≤ n-
nums中的所有值都各不相同。
示例
- 输入
- nums = [4, 2, 0, 1]
- 输出
- 3
- 解释
- 这个列表有 4 个值，所以范围是从 0 到 4。它包含 0、1、2 和 4，只有数字 3 没有匹配项。
- 输入
- nums = [1]
- 输出
- 0
- 解释
- 只有一个值时，范围是 0 和 1。列表中有 1，所以缺少 0。
- 输入
- nums = [0, 1, 2]
- 输出
- 3
- 解释
- 下面小于 3 的数字都已出现，所以缺少的数字是 3，也就是范围的上限。它不是列表的索引。
进阶
如果列表已经排序，你能用二分查找在 O(log n) 时间内找到缺失的数字吗？
提示
逐个打开提示，每个都会多透露一点。
你确切知道列表应该包含哪些数字：从
0到n的所有整数。对于这个完整范围，是否可以计算出一个数字，并将它与为列表计算出的同一个数字进行比较？从
0到n的整数之和为n(n+1)/2，而列表的和恰好比这个值少缺失的那个值。异或的作用相同，而且不会有溢出的风险，因为一个值与自身异或的结果是0。用一个不断更新的 XOR 遍历列表一次。将它初始化为
n，然后在每个索引i处，将i和nums[i]都与它进行 XOR 运算。每个出现两次的数字都会抵消，最后剩下的就是缺失的数字。
题解
你知道列表应该包含什么：从 0 到 n 的每个整数。将完整范围和列表分别归纳为一个汇总值，可以是总和，也可以是 XOR，两者的差就是缺失的数字。这样只需遍历一次，也不需要额外的内存。
检查每个候选项
结果正确，但无法在最大的测试中运行完毕
思路
按顺序取出候选数 0 到 n，并为每个候选数扫描列表。范围内的每个数字要么在列表中，要么就是答案，因此第一个找不到匹配项的候选数就是缺失的数字。
每个候选数都需要扫描最多 n 个值。当 n = 10^4 且缺口接近上限时，需要进行约 5 × 10^7 次比较。
算法
- 让
candidate从0循环到n，包含n。 - 扫描
nums，查找与candidate相等的值。 - 如果扫描时找到了它，就继续检查下一个候选值。
- 如果扫描结束时没有匹配项，就返回
candidate。
def missingNumber(nums):
n = len(nums)
for candidate in range(n + 1):
# "in" on a list scans it from the start: O(n) per candidate.
if candidate not in nums:
return candidate
return -1从预期总和中减去总和
思路
从 0 到 n 的数字之和是 n(n+1)/2。列表就是从完整的数字集合中拿掉一个数字后剩下的部分，所以它的总和恰好少了那个数字。对于 [4, 2, 0, 1]，范围内的数字之和是 4 × 5 / 2 = 10，列表的总和是 7，因此缺少的数字是 3。
只需遍历一次列表并求和：时间复杂度为 O(n)，只需一个累计总和。
算法
- 设
n为nums的长度。 - 计算完整的和
n(n+1)/2。 - 将
nums中的所有值相加。 - 返回完整的和减去列表的和。
def missingNumber(nums):
n = len(nums)
expected = n * (n + 1) // 2
return expected - sum(nums)XOR 索引与值
思路
XOR 会抵消成对的数：a ^ a 是 0，a ^ 0 是 a，而且顺序无关紧要。将索引 0 到 n 与这些值一起进行 XOR。列表中的一个数会分别作为索引和值出现一次，因此会被抵消。缺失的数只会作为索引出现，因此它就是最后剩下的数。循环会遍历索引 0 到 n-1，所以将结果初始值设为 n。
对于 [4, 2, 0, 1]：初始值为 4，然后依次 XOR 0 和 4、1 和 2、2 和 0、3 和 1。除了 3 以外，每个数都出现两次，因此最后剩下 3。运算过程中的值所需的位数不会超过表示 n 所需的位数，因此不会溢出。
算法
- 将
result设为n，也就是nums的长度。 - 对于每个索引
i，将result分别与i和nums[i]进行异或运算。 - 返回
result。
def missingNumber(nums):
# Start with n, the one index the loop below never reaches.
result = len(nums)
for i, value in enumerate(nums):
result ^= i ^ value
return result
易错点和边界情况
- 忘记考虑
n本身也可能缺失。在[0, 1, 2]中，答案是 3，它不是一个索引；使用 XOR 的方法必须从n开始。 - 范围大小使用错误。从
0到n共包含n+1个数字，所以总和是n(n+1)/2，而不是(n-1)n/2。 - 从 1 开始搜索。在
[1]中，答案是 0。 - 输入较大时，求和方法可能发生溢出。在 32 位算术中，
n(n+1)会在n超过约 46,000 后溢出。请使用 64 位算术，或使用 XOR。
常见问题3
Missing Number 的时间复杂度是多少？
求和和 XOR 两种解法的运行时间都是 O(n)，额外空间都是 O(1)：它们只读取每个值一次，并保留一个数字。对每个候选值都搜索列表需要 O(n²)，先排序再查找缺口需要 O(n log n)。
你应该使用求和公式还是 XOR？
两种方法都只需遍历一次，且只占用常量内存。求和法更容易解释，但当 n 大约超过 46,000 时，其中间乘积需要使用 64 位整数。异或运算永远不会溢出。
你能用哈希集合解决“缺失数字”问题吗？
是的。把每个值都放入集合中，然后检查从 0 到 n，并返回集合中缺少的第一个数字。这样需要 O(n) 时间，但会额外占用 O(n) 内存，而求和法和异或法可以避免这一点。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def missingNumber(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [4, 2, 0, 1]
预期输出
3