Leetcode - 41. First Missing Positive

문제

정렬이 되지 않은 integer값의 배열이 주어진다. 이 배열에 존재하지 않는 양수값 중 가장 작은 값은?
(시간복잡도 O(n)에 해결 해야한다.)

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.
Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.
Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

해결

만약 정렬을 했다면 O(nlogn)이겠지만 hashtable을 사용하면 O(n)에 가능하다. 단 모든 hashtable을 순회할때 너무 많은 순회가 이루어 질 수 있으므로, maxval값을 찾아서 거기까지만 순회한다.

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_map<int, int> table;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0)
                table[nums[i]]++;
        }
        int maxval = 0;
        for (auto it: table) {
            maxval = max(maxval, it.first);
        }
        for (int i = 1; i <= maxval; i++) {
            if (table.find(i) == table.end())
                return i;
        }
        return maxval + 1;
    }
};

아래와 같이 하면 코드가 더 효율적으로 보이나. max()함수가 더 많이 호출되기 때문에 결과적으로 더 느린 솔루션. (실제 run time: 위 113 ms, 아래 252 ms)

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_map<int, int> table;
        int maxval = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) {
                table[nums[i]]++;
                maxval = max(maxval, nums[i]);
            }
        }
        for (int i = 1; i <= maxval; i++) {
            if (table.find(i) == table.end())
                return i;
        }
        return maxval + 1;
    }
};