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

题目主要信息:

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

具体思路:

n个长度的数组，没有重复，则如果数组填满了1～n，那么缺失n+1，如果数组填不满1～n，那么缺失的就是1～n中的数字。对于这种快速查询某个元素是否出现过的问题，还是可以使用哈希表。

• step 1：使用unordered_map构建一个哈希表，用于记录数组中出现的数字。
• step 2：从1开始，遍历到n，查询哈希表中是否有这个数字，如果没有，说明它就是数组缺失的第一个正整数，即找到。
• step 3：如果遍历到最后都在哈希表中出现过了，那缺失的就是n+1.

代码实现:

class Solution {
public:
    int minNumberDisappeared(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> mp;
        for(int i = 0; i < n; i++) //哈希表记录数组中出现的每个数字
            mp[nums[i]]++;
        int res = 1;
        while(mp.find(res) != mp.end()) //从1开始找到哈希表中第一个没有出现的正整数
            res++;
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，第一次遍历数组，为$O(n)O(n)$，第二次最坏从1遍历到$nn$，为$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$，哈希表记录$nn$个不重复的元素，长度为$nn$

进阶——原地哈希：

前面提到了数组要么缺失1～n中的某个数字，要么缺失n+1。

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

可以参考如下图示：

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)$，原地哈希，以索引为指向，没有额外空间