题目
面试题 17.19. 消失的两个数字
难度困难
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:
输入: [1]
输出: [2,3]
示例 2:
输入: [2,3]
输出: [1,4]
提示：
nums.length <= 30000
分析与代码
这里一开始我想的当然是用下面这种方法, 但是可惜, 时间复杂度飙升, 直接TLE:
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]:
ans=[]
n=len(nums)
for i in range(1,3+n):
if i not in nums:
ans.append(i)
return ans
题目要求的是$O(N)$时间复杂度, $O(1)$空间复杂度, 那么就不能自己创建哈希结构了, 只能从其他思路进行分析.
位运算角度
由于这个题跟之前的一道题(136. 只出现一次的数字 - 力扣（LeetCode）)很像, 这里当然也可以借鉴一下那道题的思路, 就是使用位运算的方法1 (参考官方题解), 进行所有数字的按位异或操作, 这里需要注意的是, 题目中要找出的是两个数字, 那么nums全部异或之后还需要再对range(1,n+3)进行异或, 这样针对2n+2个数字异或之后才能保证两两相同的被异或掉,只剩下待求的两个消失的数字, 这里记为$s_1,s_2$.
于是通过异或操作我们找到了两数字的异或值$s_1\oplus s_2:=x$, 但是这还不满足两个方程两个未知量求解的原则, 我们还需要找出一个两数的关系.
这里继续沿用位运算的思路, 因为两个不同数的异或值肯定不是$0$, 否则两数相等.
除此之外, 我们还可以通过计算异或值的最低有效位(least significant bit, 为1的最低位,下称lsb. 这样取然后计算比较方便), 然后对值进行分类, 具体来说, 对于两数的异或值$x$, 可以表示成$x=x_kx_{k-1}…x_2x_1$, 设$x$的lsb为第$l$位, 则对这两个消失的数字, 其中一个的第$l$位为1,另一个的第$l$位为0, 基于此
就可以把从 $1$ 到 $n$ 的所有整数分成两类, 其中一类包含所有二进制表示的第 $l$ 位为 $0$ 的数, 另一类包含所有二进制表示的第 $l$ 位为 $1$ 的数. 可以发现：
- 对于任意一个在数组
nums中出现一次的数字, 这些数字在上述 $2n−2$ 个数字中出现两次, 两次出现会被包含在同一类中；- 对于任意一个在数组
nums中消失的数字, 即$ x_1$ 和 $x_2$, 这些数字在上述 $2n−2$ 个数字中出现一次, 会被包含在不同类中.因此, 如果我们将每一类的元素全部异或起来, 那么其中一类会得到 $x_1$, 另一类会得到 $x_2$. 这样我们就找出了这两个只出现一次的元素.
代码上可以通过先连接数组再遍历的方法, 或者两次循环, 后者速度会快一些,并且减少内存占用.
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]: # xor
xorsum = 0
n = len(nums) + 2
for num in nums:
xorsum ^= num
for i in range(1, n + 1):
xorsum ^= i
lsb = xorsum & (-xorsum) # 取最低有效位
type1 = 0
for num in nums:
if num & lsb:
type1 ^= num
for i in range(1, n + 1):
if i & lsb:
type1 ^= i
return [type1, xorsum ^ type1]
这里跟官解不一样的就是, 第二组可以不进行分类, 直接通过得到的第一个数跟$x$做异或就得到了第二个数.
求和角度
当然, 直接求和也能得到问题的答案, 不过这里又有两种技巧, 参考了2. 当然, 第一步都是先找出$s_1+s_2$, 然后去寻找第二个关系.
第一种技巧
通过公式: \(\sum_{i=1}^ni^2=\dfrac{n(n+1)(2n+1)}6,\) 找出$s_1^2+s_2^2$, 然后联立得到$s_1-s_2$的值, 解二元一次方程组即可得到答案.
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]: # math
su = ((n := len(nums)) + 2) * (n + 3) // 2 - sum(nums) # s1+s2
squ = (n + 2) * (n + 3) * (2 * n + 5) // 6 - \
sum(map(lambda x: x * x, nums)) # s1*s1+s2*s2
sm = sqrt(2 * squ - su * su)
return [int((su + sm) // 2), int(abs(su - sm) // 2)]
第二种技巧
这种方法是基于以下的事实:
消失的两个数字不相等, 则必定有一个值$\bar s=(s_1+s_2)/2$, 使得$s_i\leq\bar s,s_j\geq\bar s(i,j={1,2})$.
那么当我们遍历
nums时, 对所有小等$\bar s$的数求和, 然后用sum(range(1,s_bar+1))(或者等差求和公式)减去这个和, 就能得到第一个数.
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]: # math
n = len(nums) + 2
sumTwo = n * (n + 1) // 2 - sum(nums)
lmt = sumTwo // 2
total = 0
for i in nums:
if i <= lmt:
total += i
one = lmt * (lmt + 1) // 2 - total
return [one, sumTwo - one]
Python集合
这个办法比较骚了, 直接一行, 但是空间复杂度拉满了, 面试时候最好别用:
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]: # set
return list(set(range(1, len(nums) + 3)) - set(nums))
原地Hash
这个办法也是比较巧妙的, 参考2, 把数组的值跟索引对应起来, 于是找缺失值就成了遍历找不存在的索引, 这里用-1表示, 其中的交换那一步是思路的重点, nums[i]既是值也是索引，要达到的目的是将对应的值放到对应的索引上.
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]: # hash
nums += [-1] * 3
for i in range(n := len(nums)):
while (ni := nums[i]) != i and ni != -1:
nums[i], nums[ni] = nums[ni], nums[i]
return [i for i in range(1, n) if nums[i] == -1]
小结
这道题其实跟另外一道有异曲同工之妙:剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣（LeetCode）, 本质上都是用位运算然后分组找两个数字的方法(官方), 或者用数学联立等式找关系的方法, 最后的原地哈希算是特别精巧的办法了.