原题 3820. 未出现过的最小正整数

来源：2018年全国硕士研究生招生考试

哈希表

class Solution {
public:
    map<int, int> mp;
    int findMissMin(vector<int>& nums) {
        for (auto num : nums) {
            mp[num]++;
        }
        int res = 1;
        for (int i = 1; ; i++) {
            if (mp[i] == 0) {
                res = i;
                break;
            }
        }
        return res;
     }
};

class Solution {
public:
    bool vis[(int)(5 + 1e5)];
    int findMissMin(vector<int>& nums) {
        for (auto n : nums) {
            if (n < 1 || n > 1e5) {
                continue;
            } else {
                vis[n] = true;
            }
        }
        int res = 1;
        for (int i = 1; i <= 1e5 + 1; i++) {
            if (vis[i] == false) {
                res = i;
                break;
            }
        }
        return res;
    }
};

排序方式

class Solution {
public:
    int findMissMin(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); i ++) {
            if (nums[i] <= 0) continue;
            if (nums[i] - nums[i - 1] > 1 && nums[i] > 1) {
                return max(nums[i - 1] + 1, 1);
            }
        }
        return max(nums[nums.size() - 1] + 1, 1);
     }
};