找到给定序列中不存在的最小正整数

我试图解决下面提供的Codility中的问题,

写一个函数:

class Solution { public int solution(int[] A); }

在给定N个整数的数组A的情况下,返回A中不存在的最小正整数(大于0).

例如,给定A = [1,3,6,4,1,2],函数应返回5.

Given A = [1, 2, 3], the function should return 4.

Given A = [?1, ?3], the function should return 1.

假使,假设:

N是[1..100,000]范围内的整数; 数组A的每个元素都是[-1,000,000..1,000,000]范围内的整数.复杂:

预期的最坏情况时间复杂度是O(N); 预期的最坏情况空间复杂度是O(N)(不计算输入参数所需的存储空间).

我写下面的解决方案,性能很低,但是,我看不到这个bug.

public static int solution(int[] A) {

        Set set = new TreeSet<>();

        for (int a : A) {
            set.add(a);
        }

        int N = set.size();

        int[] C = new int[N];

        int index = 0;

        for (int a : set) {
            C[index++] = a;
        }

        for (int i = 0; i  0 && C[i] <= N) {
                C[i] = 0;
            }
        }

        for (int i = 0; i 

分数在这里提供, 



我会继续调查自己,但如果你能看得更清楚,请通知我. 

谢谢. 


1> Eran..：
如果预期的运行时间应该是线性的,则不能使用a TreeSet,它对输入进行排序,因此需要O(NlogN).因此,您应该使用a HashSet,这需要O(N)时间来添加N元素.

此外,您不需要4个循环.将所有正输入元素添加到HashSet(第一个循环)然后找到不在该集合(第二个循环)中的第一个正整数就足够了.

int N = A.length;
Set set = new HashSet<>();
for (int a : A) {
    if (a > 0) {
        set.add(a);
    }
}
for (int i = 1; i <= N + 1; i++) {
    if (!set.contains(i)) {
        return i;
    }
}

        
@ Jorge.V，因为N是输入的大小，所以不在输入中的第一个正整数最多为N + 1（如果输入数组包含1到N之间的所有数字）。因此，第二个循环最多将运行N + 1次迭代。因此，O（N）。 

2> rista404..：
Javascript的100％结果解决方案：

function solution(A) {
    // only positive values, sorted
    A = A.filter(x => x >= 1).sort((a, b) => a - b)

    let x = 1

    for(let i = 0; i