41.缺失的第一个正数

题目描述

题解

抽屉原理

public int firstMissingPositive(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        while (0 < nums[i] && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]) {
            swap(nums, i, nums[i] - 1);
        }
    }

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

    return nums.length + 1;
}

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