【2022-09-26每日一题】面试题 17.19. 消失的两个数字[Hard]
2022-09-26
2分钟阅读时长
2022-09-26每日一题：面试题 17.19. 消失的两个数字
难度：Hard
标签：位运算 、 数组 、 哈希表
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:
输入: [1]
输出: [2,3]示例 2:
输入: [2,3]
输出: [1,4]提示：
nums.length <= 30000
方法一：位运算
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func missingTwo(nums []int) []int {
xorNum, n := 0, len(nums) + 2
for _, num := range nums {
xorNum ^= num
}
for i := 1; i <= n; i++ {
xorNum ^= i
}
lsb := xorNum & -xorNum
type1, type2 := 0, 0
for _, num := range nums {
if lsb & num > 0 {
type1 ^= num
} else {
type2 ^= num
}
}
for i := 1; i <= n; i++ {
if lsb & i > 0 {
type1 ^= i
} else {
type2 ^= i
}
}
return []int{type1, type2}
}
复杂度分析
- 时间复杂度：O(n)，其中 n 是最大的整数。需要遍历的数字有 2n−2 个，共遍历两次。
- 空间复杂度：O(1)。
方法二：数学
func missingTwo(nums []int) []int {
n := len(nums) + 2
cur := n * (n + 1) / 2 // 计算n个数的和
for _, num := range nums {
cur -= num // 最终得到两个缺失数的和
}
// 根据补全后数值各不相同可知，两者必不可能同时位于t的同一侧
sum, t := cur, cur/2
cur = t * (t + 1) / 2 // 计算1...t范围内数的和
for _, num := range nums {
if num <= t {
cur -= num // 求解前面缺失的数
}
}
return []int{cur, sum-cur}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。