[leetcode] 41. First Missing Positive

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_map<int, int> hash;
        int maxNum = 0;
        
        for(int num : nums){
            if(num <= 0) continue;
            
            hash[num]++;
            maxNum = max(maxNum, num);
        }
        
        for(int i = 1; i<=maxNum; i++){
            // cout<<i<<":"<<hash[i]<<endl;
            if(!hash[i]) return i;
        }
        
        
        
        return maxNum + 1;
    }
};

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> hash(nums.begin(), nums.end());
        int maxNum = 0;
        

        
        for(int i = 1; ; i++){
            // cout<<i<<":"<<hash[i]<<endl;
            if(!hash.count(i)) return i;
        }
        
        
        
        return 0;
    }
};

처음엔 단순하게 MAP/SET을 활용해서 나타나지 않은 수를 찾았습니다.

하지만 문제의 조건엔 메모리 제약을 걸어두었기에 최적의 해는 아닙니다.

 

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int size = nums.size();
        for(int n : nums){
            while(n >= 1 && n <= size && n != nums[n - 1]){
                swap(n, nums[n - 1]);
                
                // for(int nn : nums){
                //     cout<<nn<<". ";
                // }   cout<<endl;
            }
        }
        
        for(int i = 0; i < size; ++ i){
            if(i + 1 != nums[i]) return i+1;
        }
        
        
        
        return size + 1;

    }
};

다른사람들의 풀이를 확인해보니, 위와같은 방식으로 풀이합니다.

생각지도 못한방법인데 문제에 제공된 자료구조를 그대로 사용해서 메모리를 따로 사용하지 않고 해결합니다.

이러한 테크닉을 알게된 것만으로도 충분히 많은 것을 배울 수 있습니다.