从整数列表中找到最小缺失整数的最快方法 [英] Fastest way to find smallest missing integer from list of integers

问题描述

我有一个100个随机整数的列表.每个随机整数的值都在0到99之间.允许重复，因此列表可能类似于

I have a list of 100 random integers. Each random integer has a value from 0 to 99. Duplicates are allowed, so the list could be something like

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

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

I need to find the smallest integer (>= 0) is that is not contained in the list.

我最初的解决方法是:

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;
    }
}

但是，这需要一个辅助数组来进行簿记和第二次(可能是完整的)列表迭代.我需要执行此任务数百万次(实际应用是在贪婪的图形着色算法中，在这里我需要找到具有顶点邻接表的最小未使用颜色值)，所以我想知道是否有一种聪明的方法来获取同样的结果却没有太多的开销?

But that requires a secondary array for book-keeping and a second (potentially full) list iteration. I need to perform this task millions of times (the actual application is in a greedy graph coloring algorithm, where I need to find the smallest unused color value with a vertex adjacency list), so I'm wondering if there's a clever way to get the same result without so much overhead?

推荐答案

已经一年了，但是...

It's been a year, but ...

想到的一个想法是在迭代列表时跟踪未使用值的间隔.为了使查询更有效，例如，您可以将间隔作为元组保留在二叉搜索树中.

One idea that comes to mind is to keep track of the interval(s) of unused values as you iterate the list. To allow efficient lookup, you could keep intervals as tuples in a binary search tree, for example.

因此，使用您的示例数据:

So, using your sample data:

56，1，1，1，1，0，2，6，99 ...

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

You would initially have the unused interval [0..99], and then, as each input value is processed:

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

Result (lowest value in lowest remaining interval): 3

这篇关于从整数列表中找到最小缺失整数的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！