LeetCode_原地哈希_困难_41.缺失的第一个正数-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode_原地哈希_困难_41.缺失的第一个正数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.题目

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：
输入：nums = [1,2,0]
输出：3

示例 2：
输入：nums = [3,4,-1,1]
输出：2

示例 3：
输入：nums = [7,8,9,11,12]
输出：1

提示：
1 <= nums.length <= 5 * 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/first-missing-positive

2.思路

（1）原地哈希

思路参考本题官方题解。文章来源地址https://www.toymoban.com/news/detail-436798.html

3.代码实现（Java）

//思路1————原地哈希
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        //将 nums 中的负数变为 n + 1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        //将 nums 中小于等于 n 的元素对应位置变为负数
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                //返回第一个大于 0 的元素下标 + 1
                return i + 1;
            }
        }
        /*
            执行到这里说明 [1, n] 之间的正整数都出现了
            那么没有出现的最小的正整数即为 n + 1
        */
        return n + 1;
    }
}