1
2

输入：nums = [1,2,0]
输出：3

1
2

输入：nums = [3,4,-1,1]
输出：2

1
2

输入：nums = [7,8,9,11,12]
输出：1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    /*
    ## 解题思路
    * 将nums排列为[1,2,..n]的形式，缺失的第一个正整数x，其下标为x-1;
    * 将x=nums[i]交换到nums[x](0<x<n)的位置;
    */
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i=0; i<n; i++) {
            while(nums[i]>0 && nums[i]<=n && nums[nums[i]-1] != nums[i]) {
                swap(nums[nums[i]-1], nums[i]);
            }
        }

        for(int i=0; i<n; i++) {
            if (nums[i] != i+1) {
                return i+1;
            }
        }

        return n+1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// 1. 数组中的数字如果按1,2,3,..排列,则当第i位不位i+1时,第一个缺失的正整数即为i+1;
    /// 2. 依次遍历各个元素,将在[1, n]范围内的元素调整到[0..n-1]的位置;
    /// 3. 最后再自左至右检查, 查找第一个nums[i]!=i+1的i;
    pub fn first_missing_positive(nums: Vec<i32>) -> i32 {
        let mut nums = nums;
        let n = nums.len();
        // 依次调整各个元素至对应的位置
        for i in 0..n {
            let mut ni = nums[i];
            while nums[i] > 0
                && nums[i] <= n as i32
                && nums[i] != (i + 1) as i32
                && nums[(nums[i] - 1) as usize] != nums[i]
            {
                nums.swap(i, (ni - 1) as usize);
                ni = nums[i];
            }
        }
        // 自左至右查找第一个nums[i] != i+1
        for i in 0..n {
            if nums[i] != (i + 1) as i32 {
                return (i + 1) as i32;
            }
        }
        return (n + 1) as i32;
    }
}
// @lc code=end
struct Solution;