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

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毫秒.

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

Answer 2

如果数字没有任何限制,那么您可以进行线性搜索以查找列表中的最大值并返回一个更大的数字.

如果数字确实有限制(例如max + 1和min-1可能会溢出),那么您可以使用适用于部分排序数据的排序算法.然后浏览列表,找到不连续的第一对数字v_i和v_ {i + 1}.返回v_i + 1.

要获得最小的非负整数(基于问题中的编辑),您可以:

• 使用上面的部分排序对列表进行排序.二进制搜索列表为0.从该值迭代列表,直到找到两个数字之间的"间隙".如果到达列表末尾,则返回最后一个值+ 1.

• 将值插入哈希表.然后从0向上迭代,直到找到不在列表中的整数.