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

Question

这是 [ 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 数组的情况下执行此操作吗？

谢谢雷伊

Answer 1

您的算法很高效。

只能在空间复杂度上提高。

即使用 int 变量代替数组并设置相应的位。
然后检查哪个位没有设置。你找到了丢失的号码