algorithm - 查找数组中最小的缺失数

Question

可能重复：
查找不在列表中的最小整数

我在一次采访中被问到这个问题

给定一个未排序的数组，找出丢失的最小数。假设所有数字都是正数。

输入 = {4,2,1,3,678,3432}

输出 = 5

对其进行排序是我的第一种方法。我的第二种方法是有一个布尔标志数组。第二种方法占用大量空间。

还有比这更好的方法吗？

Answer 1

假设给定数组的长度是N。您可以使用布尔标志方法，但您不需要考虑大于考虑的数字N，因为它们显然太大而不会影响答案。你也可以考虑bitmap节省一些空间。

Answer 2

unkulunkulu 的另一种解决方案如下：

k := 1
Make an array of 2^k booleans, all initially set to false
For every value, V, in the array:
  if V < 2^k then:
    set the V'th boolean to true
Scan through the booleans, if there are any falses then the lowest one indicates the lowest missing value.
If there were no falses then increment k and go to step 2.

这将在 O(n log s) 时间和 O(s) 空间中运行，其中 n 是输入数组的大小，s 是不存在的最小值。通过不在连续迭代中重新检查最低值可以提高效率，但这不会改变约束。