41 First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3
           

Example 2:

Input: [3,4,-1,1]
Output: 2
           

Example 3:

Input: [7,8,9,11,12]
Output: 1
           

Note:

Your algorithm should run in O(n) time and uses constant extra space.

3 标準解

3.1 分析

在給定的整數數組中找到最小的未出現的正整數。要求不适用額外空間。

如果使用額外空間，可以使用hashmap，這裡考慮把用該數組實作一個hashmap。對于長度為n的數組，最小的未出現的正整數不超過n+1。考慮用第i個位置上元素的符号表示正整數i+1是否出現過。

首先周遊數組，把非正整數全部指派為1，同時確定1在原數組中出現過，否則直接傳回1。此時所有元素的符号都為正。

然後再次周遊數組，如果正整數k(k<=n)出現，則把位置k-1上的元素改為負數，但絕對值不變。

最後再次周遊數組，找到第一個正數，對應的位置i+1即為所求。

3.2 代碼

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        bool start = false;
        for(auto&n : nums){
            if(n == 1)
                start = true;
            n = (n <= 0? 1:n);            
        }
        if(!start) return 1;
        
        for(auto&n : nums){
            int val = abs(n);
            if(val <= nums.size())
                nums[val-1] = -abs(nums[val-1]);
        }
        int result = 0;
        for(;result<nums.size();result++)
            if(nums[result] > 0)
                return result+1;
        return result+1;
    }
};