코딜리티 레슨4 Counting Elements 3 - 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].

Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

​

→ 이건 좀 간단합니다. 가장 작은 정수를 찾는 것이에요. 물론 0보다는 커야하고, 배열에는 존재하지 않는 수여야합니다.

 

답변

 

1. 주어진 배열 A를 순차적으로 변경하고,

2. 반복문의 index와 비교하면서 빈 값을 찾아봅니다.

 

// you can also use imports, for example:
// import java.util.*;
import java.util.Arrays;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int finN = 1;
        int compare = 1;
        
        Arrays.sort(A);
        
        for(int a : A) {
            if(a == compare) {
                compare++;
            } else {
                finN = compare;
            }
        }
        
        finN = compare;
        
        return finN;
    }
}

 

결과

 

https://app.codility.com/demo/results/trainingHV5E88-P2D/

Detected time complexity:O(N) or O(N * log(N))