arrays - 在 O(nlogn) 和 O(logn) 附加空间中找到最小的正数

Question

这是一个众所周知的问题的略微修改版本，但我似乎无法弄清楚这个问题。

We are given an array of size n that contains unsorted sequence of positive numbers with no duplicates. I'm trying to find the smallest positive number that is not contained in the array, but I can't sort or edit the array in any way. The whole thing should be in O(nlogn) time and O(logn) space complexity.

我能想到的所有解决方案都是多项式时间复杂度。

Answer 1

您可以通过对答案进行二进制搜索来解决此问题，而无需修改数组。请记住，我们正在寻找数组中不 的最小 正整数。这意味着答案不能大于 n + 1，因为我们的数组中只有 n 个数字。所以我们只需要在 1 和 n + 1 之间进行二分查找就可以找到我们的答案。

在我们的二分搜索中，我们想要回答这个问题:对于给定的数字 k，我们的数组中是否包含从 1 到 k 的每个整数？因为没有重复项，我们可以通过计算数组中小于或等于 k ​​的元素个数来解决这个问题。如果计数是 k，那么每个这样的整数都在我们的数组中；否则，至少缺少一个。

所以我们二分查找找到 k 的最小值，其中上述属性为 false。二分搜索需要 O(log n) 次迭代，每次迭代需要 O(n) 时间，总共需要 O(n log n) 时间。空间实际上是 O(1)，因为我们只需要一个用于计数的变量。