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

Question

我有一个100个随机整数的列表.每个随机整数的值都是0到99.允许重复,因此列表可能是这样的

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

我需要找到列表中未包含的最小整数(> = 0).

我最初的解决方案是:

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

我相信没有比这更快的方法了。在你的情况下你可以做的是重用vector<bool>，每个线程只需要一个这样的向量。

尽管更好的方法可能是重新考虑整个算法以完全消除这一步。也许您可以在算法的每一步中更新最少未使用的颜色？