题目
难度：★☆☆☆☆
类型：数组
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
示例
示例 1:
输入: [3,0,1]
输出: 2
示例 2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8
解答
这个问题理解起来很容易，但是也有需要注意的地方：
-
完整数组中包含0，0也是可能缺失的元素；
-
有时输入的数组看上去没有任何缺失元素，这时认为缺失数字是数组的最大值+1。
有一些原则帮助理解这道题的解决思路：
-
补全后的数组排序后是一个起点为零，终点为原数组长度+1，步长为1的等差数列，根据这个原理可以构建补上缺失数字后的理想数组。
-
通过比较理想数组list(range(len(nums)+1))与当前数组即可获得缺失值。根据比较方式不同，可以有以下办法。
方案1：排序比对
首先将数组排序，然后和补全后的理想数组一一比较，如果遇到不和谐的数字，直接返回该数字，如果没有遇到，则返回数组长度+1。
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort() # 将数组排序
for i in range(len(nums)): # 遍历数组
if i != nums[i]: # 如果遇到了断点
return i # 返回当前缺失值
return len(nums) # 缺失值是最大值
方案2：集合相减
将理想数组中各个元素组成的集合与当前数组中各个元素组成的集合相减，得到的集合中只有一个元素，这个元素就是缺失值。
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = set(range(len(nums)+1)) - set(nums) # 预期集合与实际集合做差集
return res.pop() # 得到的元素就是结果
方案3：求和相减
数值上，理想数组中所有元素的和与当前数组中所有元素的和之间的差值即为所求。
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return (1 + len(nums)) * len(nums) // 2 - sum(nums) # 预期和与当前和做差，得到的差值就是结果
方案4：异或
将理想数组和当前数组合并组成新数组，这个大数组中除了缺失值只出现过一次之外，其他数字都出现过两次，问题转化为【题目136. 只出现一次的数字】，根据异或（用符号“^”表示）的性质：
0 ^ a = a
a ^ b = b ^ a
a ^ a = 0
可以得到，只需要将新数组中所有数字求取异或的结果即为缺失数字。
这里为了节省空间，我们没有构造数组，而是直接求取：
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = 0 # 初始化一个结果变量
for i in range(len(nums)): # 遍历数组
res ^= nums[i] # 结果变量和元素中每个元素异或
res ^= i # 结果变量和预期数组的每个元素异或
res ^= len(nums) # 预期数组要多一个数，继续异或
return res # 只出现一次的数就是结果
如有疑问或建议，欢迎评论区留言~
网友评论