java - Codility MissingInteger 任务，一种情况超时

Question

任务是找到给定数组中不存在的第一个正整数。

我已经找到了正确的解决方案，但是我不明白为什么我的解决方案对于“大”输入有好处，而对于“中”输入则不好。

这是我的解决方案:

import java.util.Arrays;
import java.util.stream.*;

class Solution 
{
    public int solution(int[] A) 
    {        
        int[] a = IntStream.of(A).distinct().filter( s -> s > 0 ).toArray();
        Arrays.sort(a);
        int next = 1;

        for (int i = 0; i < a.length; i++ )
        {
            if( a[i] == next )
                next++;
            else if ( a[i] > next)
                break;
        }

        return next;
    }
}

以及结果的链接: https://codility.com/demo/results/demo8F8DDW-9BK/

Answer 1

问题规范指出预期的最坏情况时间复杂度为 O(N)，因此您无法对数据进行排序。排序是 O(N log N)。如果您的排序解决方案无论如何都被接受，显然他们的测试不够严格，或者他们最大的测试用例没有正确构建。

幸运的是，您不必对数据进行排序。您已经预先知道解决方案最多是输入数组的长度，因此只有 1 和 input.length 之间的数字才有意义。您有足够的内存来为所有这些保留 boolean 值(无论如何您已经存储了那么多整数)

public int solution (int[] input) {                                         
    boolean[] isPresent = new boolean[input.length + 1];                    
    for (int i : input) {                                                   
        if (0 < i && i < isPresent.length) {                                         
            isPresent[i] = true;                                            
        }                                                                   
    }                                                                       
    for (int i = 1; i < isPresent.length; i++) {                            
        if (!isPresent[i]) return i;                                        
    }                                                                       
    return input.length + 1;                                                
}