给定一组跳过的数字,我需要找到该集合中不存在的第 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:
现在你可以做一个重要的观察:对于任何位置 i,A[i] 的值由 B[i] + i 给出。 (在上面检查这个)。为什么是这样?好吧,对于任何位置 i,其下方缺少的数字数量是 B[i]。在它之前还有 i 个数字,这意味着小于它的值的总数是 B[i] + i。
现在你有了这个,你可以回答“第 k 个缺失的数字是多少?”形式的查询。通过使用以下算法在时间 O(log n) 中:
例如,让我们采用较早的数组:
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) 时间内解决。
希望这可以帮助!
关于algorithm - 查找集合中不存在的第 n 个数字,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/22798172/