力扣第41题-缺失的第一个正数

题目
题目连接

题解

class Solution {

    /**
     * n为数组长度。结果必定在[1, n + 1]中
     */
    public int firstMissingPositive(int[] nums) {
        // 将所有非正数都置为 n + 1
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) {
                nums[i] = nums.length + 1;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            // 如果数组中存在[1, n + 1]中的数字，将该数字前一个位置的值反转为负数用于标记
            int e = Math.abs(nums[i]);
            if (e < nums.length + 1) {
                nums[e - 1] = - Math.abs(nums[e - 1]);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            // 如果该位置的数字不是负数和零说明它没有被反转过，那它下一个位置下标就是结果
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        // 否则返回 n + 1
        return nums.length + 1;
    }
}