<分区>
Possible Duplicate:
Find the Smallest Integer Not in a List
我在面试中被问到这个问题
给定一个未排序的数组，找到缺失的最小数字。假设所有数字都是正数。
输入 = {4,2,1,3,678,3432}
输出 = 5
排序是我的第一个方法。我的第二种方法是有一个 bool 标志数组。第二种方法占用了大量空间。
还有比这更好的方法吗？
标签 algorithm
<分区>
Possible Duplicate:
Find the Smallest Integer Not in a List
我在面试中被问到这个问题
给定一个未排序的数组，找到缺失的最小数字。假设所有数字都是正数。
输入 = {4,2,1,3,678,3432}
输出 = 5
排序是我的第一个方法。我的第二种方法是有一个 bool 标志数组。第二种方法占用了大量空间。
还有比这更好的方法吗？
最佳答案
假设给定数组的长度是N。
您可以使用 bool 标志方法，但不需要考虑大于 N 的数字，因为它们显然太大而不会影响答案。您还可以考虑使用 位图 来节省一些空间。
关于algorithm - 找到数组中最小的缺失数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11156491/