最小的非负数不在可能重复的数字列表中

这是[1]的变体。我有一个N的列表（已知数值N是非负整数）。列表的上限是1024.什么是不在列表中的最小非负整数？。最小的非负数不在可能重复的数字列表中

对于离，这个名单可以是0,3,6,2,4,1,8,0,9,0 - 那么输出必须为5

我想这样做的方式这 - 我知道列表的长度不会> 1024.所以我有一个大小为1024的数组IFLAG - 然后我扫描N个数字 - 如果第i个数字是k，我设置IFLAG [k] = 1 。我还保留列表中最高数字的标签，例如MAX

在扫描列表中的所有N个数字后，我将IFLAG从1扫描到（MAX + 1），并用0标识第一个位置。是我需要的输出。

我必须反复做这个（数千甚至数百万次） - 所以，有没有更好的方法来做到这一点（可能）？我可以做到这一点，而不使用IFLAG阵列？

感谢雷伊

为了确保我理解正确，“列表的上限是1024”和“我知道列表的长度不会> 1024”。你是说，最大列表长度和上限“k”是1024？ –

在我看来，IFLAG的大小是由列表中的最大值而不是列表的长度限定的。无论如何，如果您无法对列表的排列方式作出任何假设，您必须至少检查一次列表中的每个项目。你的算法只检查一次每个项目，因此就列表长度而言效率不高（你的算法在列表长度上是O（n）） –

你可以更精确地了解什么是输入，以及上限是指什么？ –

你的方法是有效的。

它只能改善空间复杂性。

I.e.而不是数组使用变量int并设置相应的位。
然后检查哪一位没有设置。你已经找到了缺失的数字

2012-01-23 10:11:44 Cratylus

如果它几乎排序，你可以排序它在O（n）insertion sort，然后找到O（n）中第一个缺失的整数。

2012-01-23 13:53:15 jgroenen

回答