在O(n)中运行的最小缺失整数算法？

Question

什么算法可能会在数组中的O(n)时间内找到丢失的整数？

假设我们有一个数组A,其元素的值范围为{1,2,3 ... 2n}.缺少一半元素,因此A = n的长度.

例如:

A = [1,2,5,3,10],n = 5

输出= 4

Answer 1

最小的缺失整数必须在[1,...,n + 1]范围内.因此,创建一个标志数组,最初都为false,表示存在该整数.然后算法是:

1. 扫描输入数组,在遇到范围中的值时将标志设置为true.该操作是O(n).(也就是说,flag[A[i]]对于i提供的输入数组中的每个位置都设置为true A[i] <= n.)
2. 扫描标志数组以获取第一个错误标志.该操作也是O(n).第一个错误标志的索引是最小的缺失整数.

编辑:O(1)额外空间的O(n)时间算法:

如果A是可写的并且元素中有一些额外的位可用A,那么可以使用常数额外空间算法.例如,如果元素是A有符号值,并且由于所有数字都是正数,我们可以使用原始数组中数字的符号位作为标志,而不是创建新的标志数组.所以算法将是:

1. 对于i原始数组的每个位置,如果abs(A[i]) < n+1,则将值设置为A[abs(A[i])]负数.(这假设数组索引基于1.如果使用基于0的数组,则以显而易见的方式进行调整.)如果存在重复值,请不要只是否定该值A.
2. 找到第一个元素的索引A是正数.该索引是最小的缺失数字A.如果所有位置都是负数,那么A必须是{1,...,n}的排列,因此最小的缺失数是n+1.

如果元素是无符号的,但可以保持高达4 n + 1的值,那么在步骤1中,不是使元素为负,而是添加2 n + 1(假设元素<= 2 n)并使用(A[i] mod (2n+1))而不是abs(A[i]).然后在步骤2中,找到第一个元素<2 n + 1而不是第一个正元素.其他这样的技巧也是可能的.

Answer 2

您可以在O(1)额外空间中执行此操作,假设阵列上唯一有效的操作是读取元素和交换元素对.

首先请注意,问题的规范排除了数组包含重复项的可能性:它包含1到2N的一半数字.

我们执行快速选择类型算法.从m = 1开始,M = 2N + 1,并在(m + M)/ 2上旋转数组.如果数组左侧部分的大小(元素<=(m + M)/ 2)小于(m + M)/ 2 - m + 1,那么第一个缺失的数字必须在那里.否则,它必须位于数组的右侧.相应地重复左侧或右侧,直到找到丢失的数字.

每次考虑的阵列切片的大小减半,并且可以在O(n)时间和O(1)空间中完成大小为n的数组的旋转.总的来说,时间复杂度是2N + N + N/2 + ... + 1 <= 4N = O(N).