经典问题
给定一个未排序的整数数组
A
,找到其中最小的未出现的正整数。[3, 2, 1, 6, 5] -> 4
[2, 3, 4, 5] -> 1
[1, 2, 3, 4] -> 5
在这个经典问题中,你只有一个数组,可以找到很多关于这个问题的解决方案和资源,包括stackoverflow、Code Review@SE和geeksforgeeks.org。
困难版
在我的问题中,你会得到两个长度为N
的数组A
和B
。构造一个长度为N
的数组C
,其最小缺失整数是最大的可能值。 C[i]
必须是 A[i]
或 B[i]
。
A = [1, 2, 4, 3],
B = [1, 3, 2, 3] =->
C = [1, 2, 4, 3] 答案为 5
A = [4, 2, 1, 6, 5],
B = [3, 2, 1, 7, 7] =->
C = [3, 2, 1, 6, 5] 答案为 4
A = [2, 3],
B = [4, 5] =->
C = [2, 5] 答案为 1
我们如何使用最坏情况下时间和空间复杂度为O(N)
来解决这个问题?
假设:
1<= N <= 100,000
1<= A[i], B[i] <= 100,000,000