[LeetCode] First Missing Positive (Java)

leetcode.com/problems/first-missing-positive/submissions/

First Missing Positive - LeetCode

문제 : 정렬되지 않은 정수 배열이 주어지면 가장 작은 누락 된 양의 정수를 찾습니다. (1이상)

 

Example 1 : Input: nums = [1,2,0] Output: 3

Example 2 : Input: nums = [3,4,-1,1] Output: 2

Example 3 : Input: nums = [7,8,9,11,12] Output: 1

 

1.접근 아이디어 :

 

• 주어진 배열을 오름차순으로 정렬한다.
• 배열의 값이 0보다 큰 인덱스를 기준으로 누락된 자연수(1을 시작으로)를 찾기 시작한다.
• 중복되는 숫자가 있을 수 있기 때문에 Set 자료구조를 사용한다. 

- O(N^2) solution

class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        Arrays.sort(nums);
        int result = 1;
        for(int i=0; i<nums.length; i++) {
            if(nums[i] > 0) {
                for(int j=i; j<nums.length; j++) {
                    if(set.contains(nums[j])) continue;
                    if(result == nums[j]) {
                        set.add(nums[j]);
                        result++;
                    } else break;
                }
                break;
            } 
        }
        return result;
    }
}

 

 

 

2. 접근 아이디어 :

 

• 주어진 배열의 크기 만큼의 새로운 배열(1부터 시작하여 그 값이 있는지 판별하기 위한 목적)을 선언한다.
• 반복문을 통해 최댓값을 업데이트 해주고 양의 값이 존재하는 값(단, 배열의 길이보다 작은 값들에 한해서)들은 새로운 배열에 -1로 체크한다.
• 새로운 배열 인덱스를 0부터 조회하면서 -1로 체크되지 인덱스 + 1이 누락된 양의 정수 값이다.
• 그렇지 않으면, 업데이트 된 최댓값 + 1이 정답이 된다.

- O(N) space & O(N) time solution

class Solution {
    public int firstMissingPositive(int[] nums) {
        int[] arr = new int[nums.length];
        int max = 0;
        for(int i=0; i<nums.length; i++) {
            max = Math.max(max, nums[i]);
            if(nums[i] > 0 && nums[i] <= nums.length) {
                arr[nums[i] - 1] = -1;
            }
        }
        for(int i=0; i<arr.length; i++) {
            if(arr[i] != -1) return i + 1;
        }
        return max + 1;
    }
}