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

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 没有出现。

提示：

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1

算法分析

解题思路

原数组上更改n为数组长度 由题所知 没有出现的最小的正整数 区间为【1 到 length + 1】

• 1.将数据所有小于等于0的数变成len + 1
• 2.把nums[i]小于等于len的数的对应下标的数变成负数
• 3.找到nums[i] > 0的数 对应的下标 + 1 即为 没有出现的最小的正整数 未找到 即为 len + 1我们将数组中所有小于等于0的数修改为N+1；

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] <= 0) {
                nums[i] = len + 1;
            }
        }
        for (int i = 0; i < len; i++) {
            int index = Math.abs(nums[i]);
            if (index <= len) {
                nums[index - 1] = - Math.abs(nums[index - 1]);
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return len + 1;
    }
}

复杂性分析

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