Answers for "returns the smallest positive integer (greater than 0) that does not occur in a. java"

1

smallest positive integer not in array java

If the expected running time should be linear, you can't use a TreeSet, which sorts the input and therefore requires O(NlogN). Therefore you should use a HashSet, which requires O(N) time to add N elements.

Besides, you don't need 4 loops. It's sufficient to add all the positive input elements to a HashSet (first loop) and then find the first positive integer not in that Set (second loop).

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;
    }
}
Posted by: Guest on March-11-2021

Code answers related to "returns the smallest positive integer (greater than 0) that does not occur in a. java"

Code answers related to "Java"

Java Answers by Framework

Browse Popular Code Answers by Language