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

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

对于 N = 1 结果 0

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

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

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

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

最佳答案

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

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) 时间内解决。

    希望这可以帮助!

    关于algorithm - 查找集合中不存在的第 n 个数字,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/22798172/

    10-11 23:00
    查看更多