为什么即使数组不是那么大，我为什么要执行这个简单的任务却得到 Timed out 错误？

Question

我正在 codility.com 上执行任务，但出现超时错误。代码和任务描述如下。任务的文本（阵列被初始化）：class Solution { public int solution(int[] A); }即，给定阵列A的N整数，返回不发生在最小的正整数（大于0） A。例如，给定A = [1, 3, 6, 4, 1, 2]，函数应该返回5。鉴于A = [1, 2, 3]，该函数应该返回4。鉴于A = [−1, −3]，该函数应该返回1。为以下假设编写一个有效的算法：N是 [1..100,000] 范围内的整数；数组的每个元素A都是 [−1,000,000..1,000,000] 范围内的整数。class Solution {    public int solution(int[] A) {        int k;        for (int i = 1;; i++) {            final int j = i;            if (!Arrays.stream(A).anyMatch(x -> x != j)) {                k = j;                break;            }        }        return k;    }}

Answer 1

看起来您的数组A不包含任何正数。因此你的循环不会中断。

O(n log n)解决方案：

public int solution(int[] A) {

    final int solution[] = {1};

    Arrays.stream(A)

            .filter(i -> i > 0)

            .sorted()

            .forEach(i -> {

                if (i == solution[0]) {

                    solution[0]++;

                }

            });

    return solution[0];

}

O(n)解决方案：

 public int solution2(int[] A) {

    BitSet bitSet = new BitSet();

    Arrays.stream(A)

            .filter(i -> i > 0)

            .forEach(bitSet::set);

    return bitSet.nextClearBit(1);

}

Answer 2

您有一个效率低下的 O(N*m) 算法。

我建议使用不同的策略，只传递一次数组。O(n) 例如使用 BitSet 来记录存在哪些正数。然后找到 BitSet 中第一个缺失的条目。例如BitSet.nextBitClear(1)

一个更简单的解决方案是对数组进行排序并找到第一个丢失的元素，但是，这是 O(n ln n)，它较慢但可能足够快。

Answer 3

对于有效的解决方案，您应该考虑对于任何解决方案n，数组必须至少包含所有n-1正数，因此长度必须至少为n-1。这反过来又允许得出结论，解决方案永远不会大于数组长度加一。

所以我们必须记录的，是小于这个限制的正数。此外，超出该范围的每个值都会减少可用于n-1 个元素的数组元素的数量，因此，我们可以进一步缩小范围。

正如 Peter Lawrey 所建议的，您可以使用 aBitSet来记录可能的解决方案范围内遇到的值。此类还有一个高效的内置操作，用于查找与最小未遇到值匹配的第一个清除位。

public int solution(int[] a) {

    int limit = a.length;

    BitSet encountered = new BitSet();

    for(int value: a)

        if(value < 1 || value > limit) limit--; else encountered.set(value);

    return encountered.nextClearBit(1);

}