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

题目主要信息:

• 题目给定一个无序整型数组，没有重复元素，可能有负数或零，需要找出其中没有出现的最小正整数

具体思路:

n个长度的数组，没有重复，则如果数组填满了1～n，那么缺失n+1，如果数组填不满1～n，那么缺失的就是1～n中的数字。正好数组的下标有0～n-1，那我们可以用数组的下标来实现索引，代表1～n中的数字是否在数组中出现过了，这种方法也被称作原地哈希。

• step 1：先遍历数组将所有的负数都修改成n+1，因为负数是不需要的，后面我们会将遇到的1～n中的数字再改成负数标记为遇到了。
• step 2：然后再遍历数组，每当遇到一个元素绝对值不超过n时，则表示这个元素是1～n中出现的元素，我们可以将这个数值对应的下标里的元素改成负数，相当于每个出现过的正整数的下标都指向一个负数。
• step 3：最后遍历数组的时候碰到的第一个非负数的下标就是没有出现的第一个正整数，因为它在之前的过程中没有被修改，说明它这个下标的正整数没有出现过。如果所有下标都出现过了，那么就缺失n+1.

注：1～n与下标之间的关系还有一个减1，上面解析为了方便直接说对应下标了

可以参考如下图示：

代码实现:

class Solution {
public:
    int minNumberDisappeared(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++) //遍历数组
            if(nums[i] <= 0) //负数全部记为n+1
                nums[i] = n + 1;
        for(int i = 0; i < n; i++)
            if(abs(nums[i] <= n)) //对于1-n中的数字
                nums[abs(nums[i]) - 1] = -1 * abs(nums[abs(nums[i]) - 1]); //这个数字的下标标记为负数
        for(int i = 0; i < n; i++)
            if(nums[i] > 0)//找到第一个元素不为负数的下标
                return i + 1;
        return n + 1;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，多次遍历数组，都是单层循环
• 空间复杂度：$O(1)O(1)$，原地哈希，以索引为指向，没有额外空间