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

此题的难点在于复杂度，On的时间复杂度就注定基于排序的方法无法使用，那就只能使用在查找任务中效率很高的哈希表。但如果全存进去，空间复杂度又会超出，所以要考虑如何在遍历的过程中对哈希表做适当的删减。

思路：哈希表中每加入一个值，就检查是否有等于当前记录的最小值的键，如果有则删去该键并哈希表中的每个值都自加一。

关键点：用int*作为值可以简化哈希表的值自加一的循环操作。

但其实最坏情况下，这个方法的空间复杂度还是On。

#include <unordered_map>
class Solution {
  public:
    void disapear(unordered_map<int, int*>& hash, int* target) {
        while (hash.find(*target) != hash.end()) { // 检查是否有与当前最小值相等的键
            hash.erase(*target); //删除该键
            (*target)++; //哈希表中所有值自加一
        }
    }

    int minNumberDisappeared(vector<int>& nums) {
        unordered_map<int, int*> hash; //创建一个int为键，int*为值的哈希表
        int* res = new int(1); //记录未出现的最小值
        for (int i = 0; i < nums.size(); i++) {//遍历数组
            hash[nums[i]] = res; //每个都加入哈希表中
            disapear(hash, res); 
        }
        return *res;
    }
};