题解 | #没有出现的编号# 哈希表

知识点

哈希表

思路

遍历整个数组可以求出最大的负数

建立哈希表，然后从1开始查看是否存在该正数，因为最多n个数，所以尝试最多n次

时间复杂度为

AC code （C++）

#include <unordered_set>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    const int INF = 2e9;
    vector<int> findMissingAndMaxNegative(vector<int>& nums) {
        unordered_set<int> S(nums.begin(), nums.end());
        int mx = -INF, mn = 0;
        for (auto x : nums) {
            if (x < 0) mx = max(mx, x);
        }
        if (mx == -INF) mx = 0;
        for (int i = 1; ; i ++) {
            if (!S.count(i)) {
                mn = i;
                break;
            }
        }
        return {mn, mx};
    }
};