algorithm - 不在两个未排序数组的特定组合中的最小正整数

Question

经典问题

Given an unsorted array A of integers, find the smallest positive integer which doesn't exist in A.

[3, 2, 1, 6, 5] -> 4
[2, 3, 4, 5] -> 1
[1, 2, 3, 4] -> 5

在这个经典问题中，你只得到一个数组，你可以找到很多关于这个问题的解决方案和资源，包括 stackoverflow , Code Review@SE和 geeksforgeeks.org .

硬版

在我的问题中，你有两个数组，A 和 B，长度都是 N。构造一个长度为 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

Answer 1

此算法适用于 O(n)数字范围 [0..n+2] 中数字的算术运算，加上处理输入的时间。

---

• 替换所有不在 [1..n] 范围内的数字与 n+2 .这不会改变结果。
• 用标记为 1, 2, 3, ..., n-1, n, n+2 的节点构造一个图, 以及所有 0 <= i < n , 节点 A[i] 之间存在一条边和 B[i] (假设 0 索引数组)。所以图表有n+1节点和 n边缘。

现在的问题等同于找到一种方法来引导边，使得入度为 0 的最小顶点是最大可能的。

---

• 找出图中的连通分量。

• 对于每个连接的组件 v顶点和e边缘，e >= v-1 :

  • 如果 e == v-1 ，是一棵树。所有引导边的方法都会导致一个顶点的入度为 0，并且可以证明，对于树中的所有顶点，存在一种方法来引导边，使其成为唯一入度为 0 的顶点。

    方法:

    以该顶点为树根，然后使每条边都从父节点指向子节点。

    当然，最好(贪婪地)选择入度为 0 的顶点作为编号最大的顶点。

  • 如果 e >= v ，连通分量内部存在电路。然后，可以对边进行定向，使所有顶点的入度都非零。

    证明(以及构造边缘方向的方法)留给读者。