从整数列表中寻找最小缺失整数的最快方法

Question

我有一个100个随机整数的列表。每个随机整数都有一个从0到99的值。重复是允许的，所以列表可以是这样的

56, 1, 1, 1, 1, 0, 2, 6, 99...

我需要找到最小的整数(

我最初的解决方案是这样的：

vector<int> integerList(100); //list of random integers
...
vector<bool> listedIntegers(101, false);
for (int theInt : integerList)
{
    listedIntegers[theInt] = true;
}
int smallestInt;
for (int j = 0; j < 101; j++)
{
    if (!listedIntegers[j])
    {
        smallestInt = j;
        break;
    }
}

但这需要一个用于记账的辅助数组和第二次（可能是完整的）列表迭代。我需要执行这个任务数百万次（实际应用程序是在贪婪的图形着色算法中，我需要用顶点邻接列表找到最小的未使用颜色值），所以我想知道是否有一种聪明的方法可以在没有太多开销的情况下获得相同的结果？

Answer 1

由于无论如何您都必须扫描整个列表，因此您拥有的算法已经相当不错。在不测量的情况下，我能建议的唯一改进（这肯定会加快速度）是摆脱你的矢量

这样，您就不必每次都在堆上分配数组的费用，并且您可以更快地获得第一个未使用的数字（第一个0位的位置）。要找到包含第一个0位的单词，您只需要找到第一个不是最大值的单词，并且可以使用位摆弄技巧来非常快速地获得该单词中的第一个0位。

Answer 2

我相信没有比这更快的方法了。在这种情况下，您可以重用vector

虽然更好的方法可能是重新考虑整个算法，以完全消除这一步。也许您可以在算法的每个步骤中更新最不常用的颜色？

Answer 3

已经一年了，但是…

脑海中浮现的一个想法是在迭代列表时跟踪未使用值的间隔。例如，为了实现高效查找，可以将间隔作为元组保留在二进制搜索树中。

因此，使用示例数据：

< code>56，1，1，1，0，2，6，99...

您最初会有未使用的间隔 [0..99]，然后在处理每个输入值时：

56: [0..55][57..99]
1: [0..0][2..55][57..99]
1: no change
1: no change
1: no change
0: [2..55][57..99]
2: [3..55][57..99]
6: [3..5][7..55][57..99]
99: [3..5][7..55][57..98]

结果（最低剩余间隔中的最低值）：3