[数据结构与算法]leetcode 41. 缺失的第一个正数 (C++)

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

 示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

提示：

1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1

该题目要求时间复杂度在O(n)，所以将数组进行排序的思路放弃，进行以下的思考：

首先将数组中小于零，大于数组长度的数都设置为0，因为大于数组长度的数里面绝对不会有我们需要的最小正整数。

        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]<=0 || nums[i]>nums.size())
            {
                nums[i]=0;
            }
        }

然后将修改之后的数组进行变化。依次遍历每一个值，当遇到大于0的元素时，得到当前的值 t，并将该数组 t-1 位置上的值加上数组长度加1：n+1 。

由于当前的数组的值都小于等于 n，所以加上 n+1之后，可以利用当前位置（t-1）元素的值来判断 t 数字是否已经在数组里面出现（加上 n+1 是因为要区分数组里面值本来就为 n 的元素）。

        int n=nums.size();
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]%(n+1)!=0)
            {
                int t=0;
                t=nums[i]%(n+1);
                nums[t-1]+=n+1;
            }
        }

最后，遍历已经经过以上两次变化的数组。如果当遍历到位置 j 处，发现当前值小于数组长度加1（n+1），就说明 j+1 这个数字在数组中没有出现，也就是数组的最小正整数值。如果最后 j 等于数组长度 n，则说明数组包含了 1~n 所有正整数，返回值也应当为 n+1。

        int a=1,j=0;        
        for(;j<nums.size();j++)
        {
            if(nums[j]<(n+1))
            {
                // cout<<"aa"<<endl;
                a=j+1;
                break;
            }
        }
        return (j==n)?n+1:a;

将以上代码拼接完整，完整代码如下：

public:
    int firstMissingPositive(vector<int>& nums) {
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]<=0 || nums[i]>nums.size())
            {
                nums[i]=0;
            }
        }
        int n=nums.size();
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]%(n+1)!=0)
            {
                int t=0;
                t=nums[i]%(n+1);
                nums[t-1]+=n+1;
            }
        }
        int a=1,j=0;        
        for(;j<nums.size();j++)
        {
            if(nums[j]<(n+1))
            {
                // cout<<"aa"<<endl;
                a=j+1;
                break;
            }
        }
        return (j==n)?n+1:a;
    }
};