[Codility] Lesson4. MissingInteger - 문제풀이

Description

배열 A에 N개의 정수가 주어지면 A에 없는 가장 작은 양의 정수(0보다 큼)를 반환합니다.

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].

Solution 1. Sort(정렬)

public int solution(int[] A) {
    Arrays.sort(A);
    int len = A.length;
    int result = 1;
    for(int i =0; i<len; i++){
        if(A[i] < 1 || A[i] < result)continue;
        if(A[i] > result){
            return result;
        }else{
            result++;
        }
    }
    return result;
}

배열을 정렬한 후 반복하며 양수가 나오는 시점부터 1과 비교한 뒤 하나씩 더해가며 비교합니다. 가장 먼저 만나는 A[i] > result 인 경우가 비어있는 값입니다.

Reference

MissingInteger coding task - Learn to Code - Codility