41. First Missing Positive

문제: https://leetcode.com/problems/first-missing-positive/

First Missing Positive - LeetCode

 1,2,3~으로 positive number가 구성되어있는데, 주어진 배열에서 빠진 positive number 중 가장 작은 값을 linear time & constant space만에 구하는 문제다.  예를 들어보면, {1, 2, 3, 5, 6}이 주어지면 1부터 시작하는 positive number의 집합에서 빠진 수 중 가장 작은건 4이다.  만약 4도 들어가있다면 7이 답이 될 것이다.

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        
        bool isOn = true;
        while(isOn){
            isOn = false;
            for(int i = 0; i < n; i++){
                if(nums[i] <= 0){
                    nums[i] = -1;
                } else if(nums[i] > n){
                    nums[i] = -1;
                } else {
                    int next = nums[i] - 1;
                    if(nums[i] == i + 1) continue;
                    if(nums[next] == nums[i]) continue;
                    isOn = true;
                    int tmp = nums[next];
                    nums[next] = nums[i];
                    nums[i] = tmp; 
                }
            }
        }
        
        int ans = 0;
        
        for(int i = 0; i < n; i++){
            if(nums[i] != i + 1){
                ans = i + 1;
                break;
            }
        }
        return ans == 0 ? n + 1 : ans;
    }
};

 첫 번째 생각난 방법은 주어진 배열을 iteration하는데, 나오는 값이 배열의 인덱스 값 안에 들어오면 해당 값들을 swap하는 방식을 사용했다.  인덱스의 범위를 벗어나는 음수나, 인덱스 범위를 초과하면 -1로 초기화해줬다.  이렇게 swap이 일어나지 않을 때까지 반복하면 각 인덱스에 맞는 positive number(i + 1 == value)들이 들어가며 그렇지 않은 경우 다른 값 또는 음수가 들어간다.  이후 iteration으로 첫 번째 인덱스와 미스매칭되는 위치의 값을 답으로 구한다.

 

 while로 이중루프의 형식을 취하여 O(NM)의 형식을 띄지만 실제 M의 수행횟수가 많지 않아서 수행시간은 O(N)과 비슷하게 나온다.

 

Time complexity: O(NM)

Space complexity: O(1)

 

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for(int i = 0; i < n; i++){
            if(nums[i] == 1){
                ans = 1;
            }
            
            if(nums[i] <= 0 || nums[i] > n){
                nums[i] = 1;
            }
        }
        
        if(!ans) return 1;
        
        for(int i = 0; i < n; i++){
            int next = abs(nums[i]) - 1;
            if(nums[next] > 0) 
                nums[next] = -nums[next];
        }
        
        for(int i = 1; i < n; i++){
            if(nums[i] > 0){
                ans = i + 1;
                break;
            }
        }
        return ans == 1 ? n + 1 : ans;
    }
};

 positive number의 첫 번째 값은 1이므로 1이 배열에 있는지 확인한다.  이후 음수나 배열의 범위를 초과하는 수들을 1로 초기화한다.  이후 iteration하면서 value에 해당하는 index(value - 1)을 모두 음수로 초기화한다.  즉, 음수가 되는 값들은 주어진 배열에서 값이 존재한다는 뜻이다.  이후 배열에서 처음 나오는 양수의 인덱스가 First missing positive가 된다.

 

Time complexity: O(N)

Space complexity: O(1)