代码之家 › 专栏 › 技术社区 › Eziz Durdyyev

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

algorithm

Eziz Durdyyev · 技术社区 · 6 年前

经典问题

经典问题语句是:给定一个未排序的数组 A 在整数中,找到不存在于 一 。

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

在一个经典的问题语句中,只给您一个数组,您可以找到许多关于这个问题的解决方案和资源, here , here 和 here 。

硬版

在我的问题中,有两个数组, 一 和 B ,两个长度 N . 构造数组 C 长度的 n ,其“丢失的最小整数”为 最大限度 可能的。 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

我们如何解决这个问题 O(N) 最坏情况下的时间和空间复杂性?

假设:

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

2 回复 | 直到 6 年前

m69 ''snarky and unwelcoming'' 6 年前

如果对数组进行迭代并构建一个图,其中在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]

Graph:

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

我们发现循环[1>5>1]和[9>2>7>9]以及非循环子图中的最高整数8。

有向图:

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。

user202729 Nati Keidar 6 年前

这个算法适用于 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 ,所连接的组件内部存在电路。然后,可以对边进行定向,使所有顶点的度数都不为零。
  
  证明(和构造边缘方向的方法)留给读者。