문제

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

제한사항

• 1 $\leq$ nums.length $\leq$ 5 * $10^5$
• $-2^{31}$ $\leq$ nums[i] $\leq$ $2^{31}$ - 1

접근

정렬되지 않았으며 중복된 숫자가 존재하는 배열들이 주어질 때 이를 순차적으로 두었을 때 빠진 가장 작은 양수를 반환하는 문제입니다. 해쉬 테이블 기반으로 데이터를 저장하는 Hash Map을 통해 해결했어요. 가만 생각해보니 해쉬 테이블의 삽입 속도가 O(logn)이라서 문제의 조건을 충족하지 못했네요... 나중에 다시 한번 풀어봐야겠어요.

답안

class Solution {
    public int firstMissingPositive(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for(int num : nums){
            if(num < 0){
                continue;
            }
            if(countMap.containsKey(num)){
                countMap.replace(num, countMap.get(num) + 1); 
            } else {
                countMap.put(num, 1);
            }
        }

        for(int i = 1; i < Integer.MAX_VALUE; ++i){
            if(!countMap.containsKey(i))
                return i;
        }
        return Integer.MAX_VALUE;
    }
}