找出给定序列中不出现的最小正整数

Question

我试图解决下面提供的Codness中的一个问题，

编写一个函数：

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）（不计算输入参数所需的存储）。

我写的解决方案下面给出了一个低性能，但是，我看不到错误。

public static int solution(int[] A) {

        Set<Integer> 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 < N; i++) {

            if (C[i] > 0 && C[i] <= N) {
                C[i] = 0;
            }
        }

        for (int i = 0; i < N; i++) {

            if (C[i] != 0) {
                return (i + 1);
            }
        }

        return (N + 1);
    }

这里提供了分数，

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

Answer 1

我的代码在Java，100%的结果在代码

import java.util.*;

class Solution {
    public int solution(int[] arr) {
        int smallestInt = 1;

        if (arr.length == 0) return smallestInt;

        Arrays.sort(arr);

        if (arr[0] > 1) return smallestInt;
        if (arr[arr.length - 1] <= 0) return smallestInt;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == smallestInt) {
                smallestInt++;
            }
        }

        return smallestInt;
    }
}

Answer 2

100%的Javascript结果解决方案：

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 < A.length; i++) {
        // if we find a smaller number no need to continue, cause the array is sorted
        if(x < A[i]) {
            return x
        }
        x = A[i] + 1
    }

    return x
}

Answer 3

如果预期的运行时间应该是线性的，则不能使用树集，它对输入进行排序，因此需要O（NlogN）。因此，您应该使用HashSet，这需要O（N）时间来添加N元素。

此外，你不需要4个循环。将所有正输入元素添加到HashSet（第一个循环）中，然后找到不在该集合中的第一个正整数（第二个循环）就足够了。

int N = A.length;
Set<Integer> 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;
    }
}