题解 | #缺失的第一个正整数#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    //因为数组的大小为n
    //所以缺失的第一个正整数只有可能是1.。n+1之间的某一个数
    //所以对数组进行这样一种排序，即如果某一个数在1。。。n之间那就把他放到下标和这个数相同的地方去
    //按照这种方式排完序后遍历一遍数组，如果某个位置的值在1.。n之间但是和下标不相等，说明这个位置的数不存在
    int minNumberDisappeared(vector<int>& nums) {
        // write code here
        int n=nums.size();
        for(int i=0;i<n;i++){
            while(nums[i]>=1&&nums[i]<=n&&nums[i]!=i+1){
                int temp=nums[i];
                nums[i]=nums[nums[i]-1];
                nums[temp-1]=temp;
            }
        }
        //排完序后再遍历一遍nums数组
        for(int i=0;i<n;i++){
            if(nums[i]!=i+1)
                return i+1;
        }
        //如果循环结束后都没有返回值
        //说明数组中的值是一一对应的，也就是说缺少的正整数数n+1
        return n+1;
    }
};