1539. Kth Missing Positive Number

의역: 오름차순으로 정렬되어 있는 정수 배열 arr와 정수 k가 주어질 때 자연수 1부터 해당 배열의 요소들을 제외하고 카운트 할때 k번째로 오는 수를 구하라.  

 

풀이:

1. 자료구조 Set 사용

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public int findKthPositive(int[] arr, int k) {
        HashSet<Integer> map = new HashSet<Integer>();
        int count = 0; int checker = 0;
        for (int unit:arr)
            map.add(unit);
        while(checker!=k)
            if(!map.contains(++count))
                checker++;

        return count;
    }
}

2. OnePass 알고리즘 

class Solution {
    // 시간 복잡도 O(n)
    public int findKthPositive2(int[] arr, int k) {
        for (int i : arr) {
            if (i <= k) k++;
            else break;
        }
        return k;
    }
}

3. 이진 탐색 활용

class Solution {
    // 시간 복잡도 O(log n) 공간복잡도 O(1)
    // 배열 범위 내부에서 k보다 작은 것이 있다면 카운트++ 그러나 카운트가 증가하면서 새롭게
    // 배열 범위 내부에서 작은 값이 생긴다면 카운트++
    public int findKthPositiveOtimal(int []arr, int k){
        int start = 0; int end = arr.length;
        // 해당 이진 탐색으로 찾는 것 -> 1부터 카운트 하며 k까지 증가 할때 해당 값이 k보다 작아 지는
        // 수 들의 갯수
        while(start<end){
            int mid = (start+end)/2;
            // 해당 식을 통해 arr[mid]의 값이 최종적으로 카운트 했을 때의 값보다 작아짐을 확인 가능
            if(arr[mid]-mid-1<k)
                start = mid+1;
            else
                end = mid;
        }
        return k+start;
    }
}