[Codility - Java] 4. Counting Elements - 4. MissingInteger

MissingInteger

This is a demo task.

Write a function:

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

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

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

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

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

Write an efficient algorithm for the following assumptions:

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

---

N개의 정수가 들어있는 배열 A는, A 에 있지 않은 가장 작은 양의 정수를 리턴합니다.
1 <= N <= 100000 이기 때문에 배열 A는 최소 1개 이상의 요소를 가지고 있습니다.

• -100, 4, -23, 1, -11, 3, 11 -> 2
• 4, 5, 7 -> 1
• -1, -3 -> 1
• 2 -> 1

---

result에 결과의 기본값은 1로 넣고,
배열 A를 오름차순 정렬한 후

순회하면서 음수일 경우 무시
result보다 a가 더 클 경우에는 0보다 큰 가장 작은 양수값으로 간주하고 반복문을 종료합니다.
그 외의 경우에는 a + 1 값을 result에 설정합니다.

static int missingInteger(int[] A) {
    Arrays.sort(A);
    int result = 1;
    for (int a : A) {
        if(a < 0)
            continue;
        if(result < a)
            break;
        result = a + 1;
    }
    return result;
}

$O(N)$ or $O(N * log(N))$