缺失的最小正数

（此题也是计算所 VIPL 2024 机试第一题）

输入一串空格分隔的整数，输出没有在这串数中出现的最小整数。

示例：

Input：3 5 2 1 6 0 -2
Output：4

假设数组长度是 n，应该察觉到“没有出现的最小整数”的范围一定在 $[1, n + 1]$ 。可以想象，数组如果想让这个“最小整数”尽可能大，则必须从 1， 2， 3...这样填满每个位置，一旦留出空缺，那个空缺将是答案。因此当数组是 [1, 2, 3, ..., n] 时，答案就是 n + 1。

可以把数组本身当做一个哈希表，在 nums[0] 处放 1， nums[1] 处放 2，...从 0 开始遍历，只关心 $[1, n]$ 的值。nums[i] 应该放到nums[nums[i] - 1]处，至于那里原来是什么数我不管，直接交换就行。这么做完之后，我能够保证，在数组中出现的在 $[1, n]$ 的数都已经放到了对应的索引位置。然后从头开始遍历，检查nums[i] == i + 1，当不对应时的 i + 1，就是最小的缺失的正数。

最后别忘了，如果遍历完没有找到这个空缺位置，说明数组就是 [1, 2, 3, ..., n]，应当返回 n + 1。

C++27 linesExpandCollapse

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> nums;
    int x;
    
    while (cin >> x) {
        nums.push_back(x);
    }
    
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
            swap(nums[i], nums[nums[i] - 1]);
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            cout << i + 1 << endl;
            return 0;
        }
    }
    cout << n + 1 << endl;
    
    return 0;
}