algorithm - 找出集合中不存在的第 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。这是正确的:

• 第0个缺失元素为0
• 第一个缺失的元素是2
• 第二个缺失的元素是3
• 第三个缺失的元素是6
• 第 4 个缺失的元素是 7
• 第 5 个缺失的元素是 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) 的时间内解决。

希望这对您有所帮助!