力扣 41. 缺失的第一个正数

题目来源：https://leetcode-cn.com/problems/first-missing-positive/

大致题意：
给一个长度为 n 的数组，找出数组中未出现的最小的整数

思路

可知，数组中未出现的整数值最大不超过 n + 1

于是可以使用置换方法，让每个元素值为 1 - n 之间的数出现在对应索引处（即元素值 - 1 的位置）

• 对于索引 i 处的元素值 x，若 x 在 [1, n] 范围内 x != i + 1，即值与索引不匹配，将索引 i 处元素与索引 x - 1 出元素值交换
• 交换后，x 出现在匹配的索引处，但是索引 i 的值仍可能不为 i + 1，重复置换操作，直至索引 i 处的值不在区间内或者为 i + 1

于是，解题方法为：

1. 遍历数组，对所有位置进行上述置换操作
2. 遍历置换后的数组，判断当前索引与对应值是否匹配，第一个不匹配的值即为答案
3. 若数组中所有值与索引匹配，结果为 n + 1（前 n 个数都出现了）

代码：

public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
        	// 当索引 i 处的元素值在区间内且不为 i + 1 时，置换
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        // 找出最小的未出现的整数，即索引与值不匹配的最小的数
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        // 前 n 个都匹配，结果为 n+1
        return n + 1;
    }