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

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

一年过去了，但是...

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

因此，使用您的样本数据:

56, 1, 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