【数组篇】day10_41. 缺失的第一个正数

题解：

思路：

• 考虑到题目要求空间复杂度为常数，需要将nums本身作为字典表，元素值看作字典表的索引，即x = num-1
• 遍历nums数组，当元素大于0、元素值对应的索引在范围之内时，与对应索引处的元素交换位置

复杂度：

• 时间复杂度：O(n) 
• 空间复杂度：O(1)

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                // 满足在指定范围内、并且没有放在正确的位置上，才交换
                swap(nums, nums[i] - 1, i);
            }
        }

        // [1, -1, 3, 4]
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        // 都正确则返回数组长度 + 1
        return len + 1;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}