17.缺失的第一个正数

参考链接

41. 缺失的第一个正数 - 力扣（LeetCode）

41. 缺失的第一个正数 - 力扣（LeetCode） - liweiwei1419 题解

优秀题解

重新按自己理解思路写了下注释

class Solution {
    public int firstMissingPositive(int[] nums) {
        // 1、原地排序，使得 nums[下标] = 下标 + 1
        // 2、遍历数组，寻找res

        // 1️⃣
        for (int i = 0; i < nums.length; i++) {
            // 循环，直到 nums[i] 在正确的位置即：nums[nums[i] - 1] == 下标 + 1（nums[i]）；注：忽略0、负数、超过数组长度的值
            while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
                // 下标 nums[i] - 1 和 i 交换，使得 nums[i] 回归到正确位置，保证 nums[nums[i] - 1] = 下标 + 1（nums[i]）
                int tmp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = tmp;
                // 如果 nums[nums[i] - 1] != 下标 + 1，继续循环
            }
        }

        // 2️⃣
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        // 都符合的情况下
        return nums.length + 1;
    }
}