缺失的数字

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

示例 1:

输入: [1,2,0]
输出: 3

示例 2:

输入: [3,4,-1,1]
输出: 2

示例 3:

输入: [7,8,9,11,12]
输出: 1

思路

不会，学习一下

将数组视为哈希表

• 将负数设为数组长度 + 1
• 将正数对应的索引设置设为负数。如果有两个相同的正数，那么对应索引位置会是正数
• 遍历数组，返回第一个正数的下标 + 1

解答

class Solution {
    public int firstMissingPositive(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (nums[i] <= 0) nums[i] = length + 1;
        }

        for (int i = 0; i < length; i++) {
            int num = Math.abs(nums[i]);
            if (num <= length) nums[num - 1] = -Math.abs(nums[num - 1]);
        }

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