[Codility] MissingInteger

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

 

Set을 이용하게 되면 O(1) 로 중복 경우도 제거하고 값이 있는지를 찾을 수 있다.

1. sort 를 한후 가장 큰 값이 0 보다 작으면 return 값은 1이 될것이다.  
2. 그렇지 않은 경우 배열 A의 모든 원소를 중복 제거하여 Set 에 넣은 후
3. 1부터 배열 A의 최대값 + 1 까지 값이 있는지를 contains로 check 하다가 없으면 그 값이 가장 최솟값

Set 의 경우엔 contains, remove, add 등이 모두 O(1) 시간 복잡도 이므로 간단하게 해결할 수 있다. 그리고 마지막 return -1 은 두개의 if문에 모든 경우가 속하지만 return 값이 없으면 안되기 때문에 오류 체크를 위해 넣었다.

 

import java.util.*;

class Solution {
    public int solution(int[] A) {
        
        HashSet<Integer> set = new HashSet<>();
        Arrays.sort(A);
        
        if(A[A.length-1] <= 0){
            return 1;
        }
        else{
            for(int i = 0; i < A.length ; i++){
                set.add(A[i]);
            }
        }
        
        for(int j = 1; j <= A[A.length - 1] + 1; j++){
            if(!set.contains((Integer)j)){
                return j;
            }
        }
        return -1;
    }
}