找到集合中不存在的第n个数字

Question

给定一组跳过的数字,我需要找到集合中不存在的第N个数字.例:

给定[1,4,5]一些结果:

对于N = 1结果0

对于N = 2结果2(因为跳过1)

对于N = 3结果3(因为跳过1)

对于N = 4结果6(因为1,4,5被跳过)

这应该适用于相当大的N,所以直截了当的解决方案并没有完全削减它=(

Answer 1

一种方法是构建一个辅助数组,告诉您,对于数组中的每个索引,它下面缺少值的数量.例如,在这个数组中:

1 4 5 9 13  (Array A)

这个数组将是

1 4 5 9 13  (Array A)
1 3 3 6 9   (Array B)

您可以使用以下方法在时间O(n)中填写数组B:

B [0] = A [0](你知道为什么吗？)
B [n + 1] = B [n] + A [n + 1] - A [n] - 1.这看起来很神秘,但实际上非常简单.位置n + 1之前缺失的总值的数量由位置n之前缺失的值的数量(即B [n])加上位置A [n + 1]和A [n]之间缺失的元素数量给出.该值为A [n + 1] - A [n] - 1.

你现在可以做一个重要的观察:对于任何位置i,A [i]的值由B [i] + i给出.(在上面查看).为什么是这样？那么,对于任何位置i,其下方缺少的数字是B [i].在它之前还有i个数字,这意味着小于它的值的总数是B [i] + i.

现在您已经拥有了这个,您可以回答"什么是第k个丢失号码？"这一形式的查询.在时间O(log n)中使用以下算法:

在B数组中进行二进制搜索(注意它已经排序!)以找到严格大于k的第一个值.
如果该条目发生在位置0,那么答案是k.这样做的原因是你正在寻找数组中第k个最小的缺失数,并且k小于数组中的第一个条目.因此,您想要的数字是k本身.
如果那个条目发生在其他地方(例如,位置x),那么你知道x≠0,所以在它之前有一些位置,即位置x - 1.由于B [x - 1]≤k,你知道你的值想要必须介于A [x - 1]和A [x]之间.如果然后从k中减去B [x],则返回A [x - 1]和A [x]之间缺失数的索引.因此,您缺少的数字是A [x - 1] + k - B [x - 1] + 1.

例如,让我们采用早期的数组:

1 4 5 9 13  (Array A)
1 3 3 6 9   (Array B)

假设我们想要第5个最小的缺失值.我们的二进制搜索找到了这个位置:

1 4 5 9 13  (Array A)
1 3 3 6 9   (Array B)
      ^

备份一个位置需要我们:

1 4 5 9 13  (Array A)
1 3 3 6 9   (Array B)
    ^

答案应该是A [i] + k - B [i] + 1.这是5 - 3 + 5 + 1 = 8.这是正确的:

让我们做另一个:假设我们想要第6个.二进制搜索将我们带到这里:

1 4 5 9 13  (Array A)
1 3 3 6 9   (Array B)
        ^

备份一个地方:

1 4 5 9 13  (Array A)
1 3 3 6 9   (Array B)
      ^

我们想要A [i] + k - B [i] + 1 = 9 + 6 - 6 + 1 = 10.这确实是正确的答案.

总的来说,这是O(n)预处理,并且查询可以在每个时间O(log n)中求解.

希望这可以帮助!