gpt4 book ai didi

algorithm - 找出集合中不存在的第 n 个数

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:55:45 28 4
gpt4 key购买 nike

给定一组跳过的数字,我需要找到该组中不存在的第 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/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com