为什么即使数组不是那么大，我为什么要执行这个简单的任务却得到 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) {&nbsp; &nbsp; int limit = a.length;&nbsp; &nbsp; BitSet encountered = new BitSet();&nbsp; &nbsp; for(int value: a)&nbsp; &nbsp; &nbsp; &nbsp; if(value < 1 || value > limit) limit--; else encountered.set(value);&nbsp; &nbsp; return encountered.nextClearBit(1);}