41.缺失的第一个正数

题目描述

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

题解

class Solution {
    public int firstMissingPositive(int[] nums) {
        int l = 0; // l表示：[0...l-1] 也就是 l 的左边，都已经放好了对应的数 (1...l)
        int r = nums.length; // r表示：最佳预期的解也就是 r。垃圾区在 r 的右边。

        while (l < r) {
            if (nums[l] == l + 1) {
                // 情况1：当前位置 nums[l] 放的正是 l+1，符合要求
                // l 向右扩，继续看下一位
                l++;
            } else if (nums[l] <= l || nums[l] > r || nums[nums[l] - 1] == nums[l]) {
                // 情况2：遇到了“垃圾数”，需要扔到右边的垃圾区
                // 具体的垃圾定义：
                // 1. nums[l] <= l：该正数已经出现过在左边区域了，或者是负数/0，没用。
                // 2. nums[l] > r：数值太大，超过了当前可能的答案范围，没用。
                // 3. nums[nums[l] - 1] == nums[l]：这是个重复数（比如当前是5，但下标4的位置已经是5了），没用。

                // 把当前数扔给 r 位置（垃圾区扩充），r 左移，并把 r 位置还没检查的数换过来检查
                swap(nums, l, --r);
            } else {
                // 情况3：这是一个合法的正数，但它没在正确的位置上
                // 比如 nums[l] 是 5，它应该在下标 4 的位置。
                // 把它换到它该去的地方 (nums[l] - 1)
                swap(nums, l, nums[l] - 1);
            }
        }

        // 循环结束后，l 代表 [0...l-1] 都是整齐的 1...l
        // 所以缺失的第一个正数就是 l + 1
        return l + 1;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}