[Leetcode] 41. First Missing Positive

 

https://leetcode.com/problems/first-missing-positive/description/

Leetcode - First Missing Positive

문제 유형 : 배열, 정렬

문제 난이도 : Hard

 

문제

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

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

 

정렬되지 않은 정수 배열 nums가 주어집니다. nums에 없는 가장 작은 자연수를 반환하시오.

 

알고리즘을 O(n)의 시간과 O(1)의 공간 복잡도 내로 구현해야 합니다.

 

풀이

우선, 정답의 범위는 1 ~ n+1이다.

만약 n+1보다 큰 정답이 있다면, 모순된다.

배열에 양수를 1부터 꾹꾹 틀어막는다 해도, n까지이기 때문이다.

 

배열을 다음의 알고리즘으로 i번째 인덱스에 i+1이 오도록 해야 한다:

만약 현재 값이 1 ~ n이고, 현재 값이 i+1이 아니고, nums[현재값-1]과 현재 값이 다르다면, 

현재 인덱스의 값과 자리를 바꾼다. 이를 계속 반복한다.

이를 n번 실행하면, [3, 4, -1, 1]에서 [1, -1, 3, 4]로 바뀐다.

코드가 O(n^2)처럼 보일 수 있지만, 실제로 건너뛰는 게 되는 과정이 많아서 실제 런타임은 O(n)이다.

 

이제, 배열을 처음부터 다시 순회하면서, i번째 인덱스에 i+1이 없으면, i+1을 반환한다.

배열을 다 순회하고도 없으면, 답은 n+1이다.

 

코드

C++

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        const int n = nums.size();

        for(int i = 0; i < n; i++) {
            int x = nums[i];

            while(x >= 1 && x <= n && x != i+1 && nums[x-1] != x) {
                swap(nums[x-1], nums[i]);
                x = nums[i];
            }
        }

        for(int i = 0; i < n; i++) {
            if(nums[i] == i+1) continue;
            return i+1;
        }

        return n+1;
    }
};