查找未排序数组中缺少的最小正整数，硬版

Question

经典的问题陈述是：给定一个未排序的整数数组A，找到A中不存在的最小正整数。

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

在一个经典的问题陈述中，你只得到一个数组，你可以在这里、这里和这里找到很多关于这个问题的解决方案和资源。

在我的问题中，你得到了两个数组，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] answer = 5
A = [4, 2, 1, 6, 5], B = [3, 2, 1, 7, 7] =-> C = [3, 2, 1, 6, 5] answer = 4
A = [2, 3], B = [4, 5] =-> C = [2, 5] answer = 1

我们如何以< code>O(N)的最坏情况时间和空间复杂度解决这个问题？

假设：

1<= N <= 100,000
1<= A[i], B[i] <= 100,000,000

Answer 1

请检查这个代码片段，我已经写在Java8

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;
import java.util.stream.IntStream;


public class Run {
    private int solution(int[] A) {

        List<Integer> positiveIntegerList = Arrays.stream(A).distinct().filter(e -> e > 0).boxed().sorted(Comparator.naturalOrder()).collect(Collectors.toList());
        final int i = 1;

        if (!positiveIntegerList.isEmpty()) {
            final int missingMax = positiveIntegerList.get(positiveIntegerList.size() - i) + i;
            List<Integer> range = IntStream.rangeClosed(i, positiveIntegerList.get(positiveIntegerList.size() - i))
                    .boxed().collect(Collectors.toList());

            AtomicInteger index = new AtomicInteger();
            return range.stream().filter(e -> !e.equals(positiveIntegerList.get(index.getAndIncrement()))).findFirst().
                    orElse(missingMax);
        } else {
            return i;
        }
    }


    public static void main(String[] args) {
        Run run = new Run();
        int[] intArray = new int[]{1, 3, 6, 4, 1, 2};
        System.out.println(run.solution(intArray));
    }
}

Answer 2

如果遍历数组并构建一个图，其中在a或B中遇到的每个唯一整数都成为一个顶点，并且每对整数a[i]和B[i]在两个顶点之间创建一条边，则该图最多有2×N个顶点，因此该图所占用的空间与N成线性关系。

然后，对于图中的每一条边，我们将决定其方向，即它连接的两个整数中的哪一个将用于数组C。最后，我们将再次迭代数组，对于每一对整数，我们查看图中相应的边，以了解要使用的整数。

我相信决定图中方向所需的操作都可以在线性时间内完成到N（如果我错了，请纠正我），所以整个算法应该具有O（N）的时间和空间复杂度。

决定图形中边方向的规则如下:

• 图中未连接的部分分别处理
• 如果（子）图的边比顶点少（即它有一个没有循环的树结构），则必须牺牲最高的整数：将边指向远离该顶点的方向，并在其余顶点上传播该方向
• 如果（子）图的边多于顶点（即，它至少包含一个循环，可以是由多条边连接的两个顶点），则找到任何循环，并为其边指定相同的方向（顺时针或逆时针）；然后将方向传播到其他顶点

在遍历数组并查找图形中相应的边时，标记当两个顶点多重连接时已使用的整数，以便第二次使用另一个整数。之后，你可以选择其中之一。

例：

A = [1,6,2,9,7,2,5,3,4,10]
B = [5,8,3,2,9,7,1,2,8,3]

图表:

1===5   6---8---4   9---2===3---10
                    |   |
                    --7--

我们找到周期 [1

有向图:

1<=>5   6<--8-->4   9-->2<=>3-->10
                    ^   |
                    |-7<-

结果：

C = [1,6,2,2,9,7,5,3,4,10]

缺少的第一个整数是8，因为我们不得不牺牲它来保存[6,8,4]子图中的4和6。

Answer 3

此算法适用于对数字范围[0..n2]内的数字进行的O（n）算术运算，以及处理输入的时间。

• 将所有不在范围[1… n]内的数字替换为n 2。这不会改变结果。
• 构造一个节点标记为1,2,3，…， n-1， n， n 2的图，对于所有0

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

>

在图表中找到连接的组件。

对于具有 v 个顶点和 e 个边的每个连接元件，e

>

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

方法：

将树的根定在那个顶点，然后使每条边都从父节点指向子节点。

当然，最好（贪婪地）选择度数为0的顶点作为数量最多的顶点。

如果 e

证明（和构造边缘方向的方法）留给读者。