题目难度: 困难
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
-
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
-
以任意顺序返回这两个数字均可。
示例 1:
- 输入: [1]
- 输出: [2,3]
示例 2:
- 输入: [2,3]
- 输出: [1,4]
提示：
- nums.length <= 30000
题目思考
- 如何利用数字是 1 到 N 的条件?
解决方案
思路
- 分析题目, 一个很容易想到的方案就是将输入数字转成集合, 然后依次遍历 1 到 N, 查找不在集合的数字
- 这样虽然时间复杂度是 O(N), 但空间复杂度也是 O(N), 不满足题目要求, 如何优化空间复杂度呢?
- 这里我们可以通过原地操作来更新数字的存在情况, 从而模拟上述思路中的集合, 具体思路如下:
- 注意到数字都在 1 到 N 范围内, 且各不相同, 所以每个数字唯一对应一个下标, 对应关系就是数字 x=下标 x-1
- 所以我们只需要将对应下标处的值更新成其绝对值的相反数, 就可以表示其存在于原始数组中 (因为已有数字都是正数)
- 标记完成后, 我们只需要再次遍历一遍数组, 找出值仍为正数的下标, 其下标加 1 显然就是消失的数字
- 另外由于原数组长度是 N-2 (缺失了 2 个), 所以我们需要额外填充两个任意正数放到最后, 保证可以正常更新 1 到 N 的任意数字对应的下标
- 注意在更新存在状态时, 只遍历原始数组长度(即 N-2), 需要忽略额外填充的数字, 因为它们实际并不存在于原始数组
- 另外由于某个数字可能已被更新成负数, 所以需要先取绝对值, 然后再减 1 作为待标记的下标
- 举个 🌰: 假设输入数组是[2,3]
- 那么说明数字范围是 1 到 4
- 这里先额外追加两个正数, 扩充数组为[2,3,1,1]
- 然后先进行标记, 这里只遍历原始数组部分, 即[2,3]
- 先遍历到 2, 会标记下标(abs(2)-1, 即 1)处的数字为负数, 即变成[2,-3,1,1]
- 接下来遍历到-3, 会标记下标(abs(-3)-1, 即 2)处的数字为负数, 即变成[2,-3,-1,1]
- 最后再检查标记情况, 很显然下标 0 和下标 3 处的数字仍为正数, 表示原始数组不存在数字 1 和 4
- 下面代码有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(N): 只需要遍历数组两次 - 空间复杂度
O(1): 只使用了常数额外空间
代码
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]:
# 扩充两正数+负数标记
# 先扩充两位正数, 用于判断最后两个数字的存在情况
nums.extend([1, 1]) # 这里使用任意正数都可以
# 然后遍历原始数组 (不包含扩充部分), 更新存在情况
for x in nums[:-2]:
# 注意x可能已经被更新成负数了, 这里取绝对值
i = abs(x) - 1
# 将对应下标的数字更新成其绝对值的相反数, 将其标记为存在
nums[i] = -abs(nums[i])
# 最后值仍为正数的下标对应的数字就是缺失的数字
res = []
for i in range(len(nums)):
if nums[i] > 0:
res.append(i + 1)
return res
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号