【LeetCode】找出数组中第一个缺失的正整数：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.

1. 解法1

解题思路：

• 如果未限制使用空间，这道题用hash map最简单.

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_map<int, bool> unMap;
        int n = nums.size();
        int max = INT_MIN;
        
        for(int i = 0; i < n; i++) {
            unMap[nums[i]] = true;
            if(nums[i] > max)
                max = nums[i];
        }
        
        int i;
        for(i = 1; i <= max; i++) {
            if(!unMap.count(i)) {
                break;
            }
        }
        
        return i;
    }
};

2. 解法2

解题思路：

• 如果限制了使用空间，这道题只能采用覆盖愿数组的方式，本质上是桶排序。
• 第一次遍历数组，遍历到下标i时，如果nums[i]在区间[1, n]，且nums[nums[i] - 1]  != nums[i]时， 需要循环将num[i]和nums[nums[i] - 1]进行交换，以使得nums[nums[i] - 1] = nums[i]；如果不在该区间内，直接跳过。
• 第二遍历数组，找出nums[i] != i+1的整数，其中i+1即为缺失的整数。原因是，如果数组遍历完成后，下标为i的位置存储的值还不是i+1，那说明该正整数在原数组中不存在。
• 代码如下

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