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

方法一：原地哈希

具体做法：

• step 1：我们可以先遍历数组将所有的负数都修改成n+1。
• step 2：然后再遍历数组，每当遇到一个元素绝对值不超过n时，则表示这个元素是1～n中出现的元素，我们可以将这个数值对应的下标里的元素改成负数，相当于每个出现过的正整数，我们把与它值相等的下标都指向一个负数，这就是类似哈希表的实现原理的操作。
• step 3：最后遍历数组的时候碰到的第一个非负数，它的下标就是没有出现的第一个正整数，因为它在之前的过程中没有被修改，说明它这个下标对应的正整数没有出现过。

时间复杂度：o(n)

空间复杂度：o(1)

class Solution {
  public:
    int minNumberDisappeared(vector<int>& nums) {
        int size = nums.size();

        //负数置为size+1
        for (int i = 0; i < size; i++) {
            if (nums[i] < 0)
                nums[i] = size + 1;
        }
        //将数组中数字对应的下标数字置为负数
        for (int i = 0; i < size; i++) {
            if (abs(nums[i]) > 0 && abs(nums[i]) <= size)
                nums[abs(nums[i]) - 1] = -1 * nums[abs(nums[i]) - 1];
        }
        //依然是正数的下标就是没有出现的最小正整数
        for (int i = 0; i < size; i++) {
            if (nums[i] > 0)
                return i + 1;
        }
        //如果数组恰好时从1开始的递增序列，输出size
        return size + 1;
    }
};

方法二：排序

1、先对数组进行排序；

2、排序后的数组就很容易查找不存在的最小正整数。

时间复杂度：o(n)

空间复杂度：o(1)

class Solution {
  public:
    int minNumberDisappeared(vector<int>& nums) {
	  	//对数组进行排序
        sort(nums.begin(), nums.end());

        int temp = 1;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] <= 0)
                continue;

            if (nums[i] == temp) {
                temp++;
                continue;
            } else {
                return temp;
                break;
            }
        }
        return temp;
    }
};