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

Question

我试图解决这个问题:

Write a function:

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

that, given an array A of N integers, returns the smallest positiveinteger (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return5.

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

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

Assume that:

N is an integer within the range [1..100,000]; each element of array Ais an integer within the range [−1,000,000..1,000,000]. Complexity:

expected worst-case time complexity is O(N); expected worst-case spacecomplexity is O(N) (not counting the storage required for inputarguments).

我在下面编写了性能较低的解决方案，但是，我看不到错误。

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

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

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

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;
    }
}