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

思路一：sort+数据匹配。

class Solution {
public:
    int minNumberDisappeared(vector<int>& nums) {
        if (!nums.size()) {
            return 0;
        }
        int minval = 1;
        
        sort(nums.begin(), nums.end());
        
        for_each(nums.begin(), nums.end(), [&minval](const int& e) {
            if (e == minval) ++minval;
        });
        return minval;
    }
};

分析：T(n) = O(nlogn), S(n) = O(1).未满足题目要求。

思路二：使用数组下标记录元素值。若一元素出现，该元素值对应的下标元素会被标记，如负值。也可以交换数据。（注：非本人所想，思想与代码均来自排行榜。码主要求，立马删除）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int minNumberDisappeared(vector<int>& nums) {
        // write code here
        int len=nums.size();
        for(int i=0;i<len;i++)
        {
            if(nums[i]<=0)
            nums[i]=len+1;
        }
        for(int i=0;i<len;i++)
        {
           int m=abs(nums[i]);
           if(m<=len)//只有<len的实际才有用
           {
              nums[m-1]=-abs(nums[m-1]);//确保改后是负数因为可能出现z数组有l多个相同的数字
           }
        }
        for(int i=0;i<len;i++)
        {
            if(nums[i]>0)
            return i+1;
        }
        return len+1;
    }
};

分析：T(n) = O(n), S(n) = O(1).