Rooted In Develop

[Codility] Counting Elements - MissingInteger / Java 본문

Algorithm Test/Java

[Codility] Counting Elements - MissingInteger / Java

RootedIn 2020. 6. 14. 17:23

1. 문제

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.

2. 코드

import java.util.*;

class Solution {
    public int solution(int[] A) {
        
        HashSet<Integer> set = new HashSet<>();
        
        for(int i=0; i<A.length; i++) {
            if(A[i] > 0)
                set.add(A[i]);
        }
        
        if(set.size() == 0)
            return 1;

        int num = 1;
        
        while(true) {
            
            if(!set.contains(num)) {
                return num;
            }
            
            num++;
        }
    }
}
Comments