题解 | #数组中未出现的最小正整数#

#include<iostream>
#include<vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums;
    int num;
    while(n-- > 0) {
        cin >> num;
        nums.push_back(num);
    }
    int left = 0;//    已经出现的数
    int right = nums.size();//    右边界，不可能是最小未出现的正整数
    while(left < right) {
        if(nums[left] == left + 1) {//    出现新的最小正整数
            left++;
        }
        else if(nums[left] <= left || nums[left] > right  || nums[nums[left] - 1] == nums[left]) {
            //    已经出现的数 || 不可能的结果 || 当前数应该在的位置上就是该数
            nums[left] = nums[--right];
        }
        else swap(nums[left], nums[nums[left] - 1]);//    把left位置数移到正确的位置上，上边判断需要排除这两个位置的数相等的情况
    }
    cout << left + 1 <<endl;
    return 0;
}