logo标签列表

寻找列表中未出现的最小非负整数的算法

algorithmsortinginteger
3
给定一个整数列表，如何最好地找到一个不在列表中的整数？该列表可能非常大，并且整数可能很大（即BigIntegers，而不仅仅是32位int）。如果有任何区别，列表“可能”已排序，即99％的时间它将被排序，但我不能依赖始终排序。要澄清的是，给定列表{0，1，3，4，7}，可接受解决方案的示例为-2、2、8和10012，但如果有一种算法可以在不需要对整个列表进行排序的情况下找到最小的非负解（即2），我更愿意使用该算法。
你需要的是列表中最小的（正）整数，还是任何不在列表中的整数？ - rslite
你想要找到列表中最小的正整数吗？指定的整数是哪一个？ - Joe Phillips
“可能已排序”意味着完全排序将非常快速。根据“未排序”和“已排序”列表的算法，这可能值得一试。 - Albert
14个回答
6
一种简单的方法是迭代列表以获取最高值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;
}

我做了一项性能测试，创建了包含100000个从0到19999的随机数字的列表，平均最小数约为150。在测试运行中（每个测试列表有1000个），该方法平均在8.2毫秒内找到未排序列表中的最小数，在排序列表中平均为0.32毫秒。
（我没有检查该方法离开列表的状态，因为它可能会交换其中的一些项目。至少它保留了包含相同项目的列表，并且随着每次搜索将更小的值向下移动，我认为它实际上应该变得更加排序。）
如果items = {1, 2, 3}，你的解决方案会返回0。但是需求不是要求数字必须为正数吗？ - David Klempfner
6
如果数字没有任何限制，那么您可以进行线性搜索以找到列表中的最大值，并返回比该数字大1的数字。
如果数字有限制（例如max+1和min-1可能会溢出），则可以使用适用于部分排序数据的排序算法。然后遍历列表，找到第一对不连续的数字v_i和v_{i+1}。返回v_i + 1。
要获取最小的非负整数（基于问题中的编辑），您可以选择：
- 使用上述部分排序的方法对列表进行排序。二分搜索列表以查找0。从此值开始迭代列表，直到找到两个数字之间的“间隙”。如果到达列表末尾，则返回最后一个值+1。 - 将值插入哈希表中。然后从0开始迭代，直到找到不在列表中的整数。
2

我在正确性和性能方面均获得了100%的分数，你应该使用快速排序，其复杂度为N log(N)。这是你需要的内容...

    public int solution(int[] A) {
    if (A != null && A.length > 0) {
        quickSort(A, 0, A.length - 1);
    }

    int result = 1;
    if (A.length == 1 && A[0] < 0) {
        return result;
    }

    for (int i = 0; i < A.length; i++) {
        if (A[i] <= 0) {
            continue;
        }
        if (A[i] == result) {
            result++;
        } else if (A[i] < result) {
            continue;
        } else if (A[i] > result) {
            return result;
        }
    }

    return result;
}

private void quickSort(int[] numbers, int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high - low) / 2];

    while (i <= j) {
        while (numbers[i] < pivot) {
            i++;
        }
        while (numbers[j] > pivot) {
            j--;
        }

        if (i <= j) {
            exchange(numbers, i, j);
            i++;
            j--;
        }
    }
    // Recursion
    if (low < j)
        quickSort(numbers, low, j);
    if (i < high)
        quickSort(numbers, i, high);
}

private void exchange(int[] numbers, int i, int j) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
}
1
这是唯一一个在Codility演示测试中获得100％正确性和性能的解决方案。这应该被接受为答案。 - David Klempfner
2

除非它已经排序，否则您将不得不进行线性搜索，逐个查找匹配项，直到找到匹配项或到达列表末尾。如果您可以保证已排序，则始终可以使用二进制搜索的数组方法或自己编写二进制搜索。

或者像Jason提到的那样，总是有使用Hashtable的选项。

2
“probably sorted”意味着您必须将其视为完全未排序。当然，如果您能保证它已经排序，那么这很简单。只需查看第一个或最后一个元素，并加上或减去1即可。
不是真的：有些算法在假设输入已排序的情况下表现得更好，如果输入最终没有排序，则稍微差一些（与QuickSort相反，它在已排序的输入上表现最差）。 - Konrad Rudolph
1

除非您100％确定列表已排序，否则最快的算法仍然必须至少查看列表中的每个数字一次，以至少验证数字不在列表中。

1
理论上，找到最大值并加1。假设您受到BigInteger类型的最大值的限制，如果未排序，请对列表进行排序并查找间隙。
1

你是否正在寻找一种在线算法（因为你说输入是任意大的）？如果是这样，请看一下Odds算法。

否则，如已经建议的那样，对输入进行哈希处理，搜索并打开/关闭布尔集合元素（哈希索引到集合中）。

1

有几种方法：

  • 在列表中找到最大的整数并将其存储在x中。 x + 1不会在列表中。使用min()和x-1也是一样的。

  • 当N是列表的大小时，分配一个大小为(N+31)/32的int数组。对于列表中的每个元素，在数组索引i/32处设置位v&31（其中v是元素的值）的整数。忽略i/32 >= array.length的值。现在搜索第一个数组项“！= 0xFFFFFFFF”（对于32位整数）。

1

如果您无法保证它已排序，则最佳时间效率为O(N)，因为您必须查看每个元素以确保您的最终选择不在其中。那么问题就是：

  1. 可以在O(N)内完成吗？
  2. 最佳空间效率是什么？

Chris Doggett的解决方案是找到最大值并加1，既具有O(N)的时间效率，又具有空间效率（O(1)的内存使用）。

如果您只想要可能的最佳答案，那么这是一个不同的问题。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接