查找不在列表中的最小非负整数的算法

Question

给定一个整数列表，我怎样才能最好地找到列表中不的整数？

列表可能非常大，并且整数可能很大(即 BigIntegers，而不仅仅是 32 位整数)。

如果有什么不同的话，列表是“可能”排序的，即 99% 的时间它将被排序，但我不能依赖总是被排序。

编辑 -

澄清一下，给定列表 {0, 1, 3, 4, 7}，可接受的解决方案示例为 -2、2、8 和 10012，但我更愿意找到最小的非负解决方案 (即 2) 如果有一种算法可以找到它而无需对整个列表进行排序。

Answer 1

一种简单的方法是迭代列表以获得最高值 n，然后您知道 n+1 不在列表中。

编辑:

找到最小未使用正数的方法是从零开始并扫描列表以查找该数字，如果找到该数字则重新开始并增加。为了使其更高效，并利用列表被排序的高概率，您可以将小于当前的数字移动到列表的未使用部分。

此方法使用列表的开头作为较低数字的存储空间，startIndex 变量跟踪相关数字的开始位置:

public static int GetSmallest(int[] items) {
    int startIndex = 0;
    int result = 0;
    int i = 0;
    while (i < items.Length) {
        if (items[i] == result) {
            result++;
            i = startIndex;
        } else {
            if (items[i] < result) {
                if (i != startIndex) {
                    int temp = items[startIndex];
                    items[startIndex] = items[i];
                    items[i] = temp;
                }
                startIndex++;
            }
            i++;
        }
    }
    return result;
}

我做了一个性能测试，我创建了包含从 0 到 19999 的 100000 个随机数的列表，这使得平均最低数字在 150 左右。在测试运行中(每个有 1000 个测试列表)，该方法找到了未排序列表中的最小数字平均 8.2 毫秒，排序列表平均 0.32 毫秒。

(我没有检查该方法在什么状态下离开列表，因为它可能会交换其中的一些项目。它离开包含相同项目的列表，至少，并且当它在列表中移动较小的值时，我认为它实际上应该针对每次搜索变得更加排序。)