Contents

1. 1. 题意：
2. 2. 解：

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

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

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

题意：

给定一个无序的整数数组，怎么找到第一个大于0，并且不在此数组的整数。
比如[1,2,0]返回3，[3,4,-1,1]返回2，[1, 5, 3, 4, 2]返回6，[100, 3, 2, 1, 6,8, 5]返回4。
**要求使用O(1)空间和O(n)时间。**

解：

借用基数排序的思路解决

class Solution {
public:

    int solve(vector<int>& nums)    {
    
        if(nums.empty() || nums.size() == 0)
            return 1;

        for(int i = 0; i < nums.size(); i++){
            // nums[i] > 0 && nums[i] <= nums.size() : 因为是正数要求数据在[1, n]的范围内
            // nums[i] != i+1 ：要求nums[i]里放i+1
            // nums[i] != nums[nums[i] - 1] ：如果nums[nums[i] - 1]里放的已经是nums[i]，则停止交换
            while(nums[i] > 0 && nums[i] <= nums.size() && nums[i] != i+1 && nums[i] != nums[nums[i] - 1]){
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        int i;
        for(i = 0; i < nums.size(); i++){
            if(nums[i] != i + 1)
                break;
        }
        return i + 1;
    }

    int firstMissingPositive(vector<int>& nums) {
        return solve(nums);
    }

};