题目
面试题 17.19. 消失的两个数字
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:
输入: [1]
输出: [2,3]
示例 2:
输入: [2,3]
输出: [1,4]
提示：
题解1
思路
- 将数组排序，若
n
u
m
s
[
i
]
?
n
u
m
s
[
i
?
1
]
≠
1
nums[i]-nums[i-1] \ne 1
nums[i]?nums[i?1]=1则说明
n
u
m
s
[
i
]
?
1
nums[i]-1
nums[i]?1不在数组中
- 同时将消失的数字在数组首和数组尾两种情况单独考虑
代码
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]:
if not nums: return [1,2]
elif len(nums) == 1:
if nums[0] == 1: return [2,3]
elif nums[0] == 2: return [1,3]
elif nums[0] == 3: return [1,2]
else: assert False
nums.sort()
ret = []
if nums[0] > 2: return [1,2]
elif nums[0] == 2: ret.append(1)
i = 1
while i < len(nums):
if nums[i] - nums[i-1] > 1:
ret.append(nums[i] - 1)
i+=1
if len(ret) == 0:
ret.append(nums[-1] + 1)
ret.append(nums[-1] + 2)
elif len(ret) == 1:
ret.append(nums[-1] + 1)
return ret
复杂度
- 时间复杂度：
O
(
n
log
?
n
)
O(n\log n)
O(nlogn)
- 空间复杂度：
O
(
log
?
n
)
O(\log n)
O(logn)
题解2
思路
- 数组的长度为
n
n
n则说明
[
1
,
n
+
2
]
[1,n+2]
[1,n+2]区间内，不曾出现过的数则说明消失了
代码
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]:
visited = [False] * (len(nums)+2)
for n in nums:
visited[n-1] = True
ret = []
for i in range(len(visited)):
if not visited[i]: ret.append(i+1)
return ret
复杂度
- 时间复杂度：
O
(
n
)
O(n)
O(n)
- 空间复杂度：
O
(
n
)
O(n)
O(n)
题解3
思路
- 假设数组消失的数为
x
1
,
x
2
x_1, x_2
x1?,x2?，则
x
1
+
x
2
=
∑
n
u
m
?
∑
(
r
a
n
g
e
(
1
,
n
+
2
)
)
x_1+x_2=\sum num - \sum(range(1, n+2))
x1?+x2?=∑num?∑(range(1,n+2))
- 若输入为哈希表，则可以通过
x
1
?
n
u
m
s
∧
x
2
?
n
u
m
s
x_1 \notin nums \land x_2\notin nums
x1?∈/nums∧x2?∈/nums来判断 可惜不是╮(╯▽╰)╭
代码
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]:
s = set(nums)
n = len(s)
currentSum = sum(s)
expectSum = (n+2)*(n+3)//2
diff = expectSum - currentSum
for i in range(1, n+3):
if i not in s and (diff - i) not in s and (diff-i)<n + 3: return [i, diff-i]
复杂度
- 时间复杂度：
O
(
n
)
O(n)
O(n)
- 空间复杂度：
O
(
n
)
O(n)
O(n)
题解4
思路
-
继题解3，考虑构造线性无关方程组，考虑：
{
a
=
x
1
+
x
2
=
(
n
+
2
)
(
n
+
3
)
2
?
∑
(
n
u
m
s
)
b
=
x
1
2
+
x
2
2
=
(
n
+
2
)
(
n
+
3
)
(
2
n
+
5
)
6
?
∑
n
?
∈
n
u
m
s
(
n
2
)
\left\{\begin{aligned} & a = x_1+x_2 = \frac{(n+2)(n+3)}{2} - \sum(nums)\\ & b = x_1^2 + x_2^2 = \frac{(n+2)(n+3)(2n+5)}{6} -\sum_{n \ \in nums}(n^2)\\ \end{aligned}\right.
?
?
???a=x1?+x2?=2(n+2)(n+3)??∑(nums)b=x12?+x22?=6(n+2)(n+3)(2n+5)??n?∈nums∑?(n2)? -
可以求解
δ
=
2
b
?
a
2
{
x
1
=
a
+
δ
2
x
1
=
a
?
δ
2
\delta = \sqrt{2b-a^2}\\ \left\{\begin{aligned} & x_1 = \frac{a + \delta}{2} \\ & x_1 = \frac{a - \delta}{2} \end{aligned}\right.
δ=2b?a2
??
?
???x1?=2a+δ?x1?=2a?δ??
代码
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]:
n = len(nums)
currentSum = sum(nums)
currentSquareSum = sum(map(lambda x: x*x, nums))
expectSum = (n+2)*(n+3)//2
expectSquareSum = (n+2)*(n+3)*(2*n+5)//6
a = expectSum - currentSum
b = expectSquareSum - currentSquareSum
delta = math.sqrt(2 * b - a * a)
return [int((a + delta)//2), int((a-delta)//2)]
- 时间复杂度：
O
(
n
)
O(n)
O(n)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
题解5
思路
- 对所有数和
[
1
,
n
+
2
]
[1,n+2]
[1,n+2]中的所有数位运算，最后得到的结果为
x
1
⊕
x
2
x_1 \oplus x_2
x1?⊕x2?
- 因为python中负数使用补码表示，所以可以使用
x
o
r
s
u
m
⊕
?
x
o
r
s
u
m
xorsum \oplus -xorsum
xorsum⊕?xorsum作为掩码进行分类
- 分组后再通过掩码计算分别求出两个不同的数
代码
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]:
xorSum = 0
for n in nums:
xorSum ^= n
for n in range(1, len(nums) + 3):
xorSum ^= n
mask = xorSum & (-xorSum)
n1, n2 = 0,0
for n in nums:
if n&mask:
n1 ^= n
else:
n2 ^= n
for n in range(1, len(nums) + 3):
if n&mask:
n1 ^= n
else:
n2 ^= n
return [n1,n2]
复杂度
- 时间复杂度：
O
(
n
)
O(n)
O(n)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
|