LeetCode_原地哈希_困难_41.缺失的第一个正数

小灰灰 2023-10-09 21:29 29阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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 \* 105  
\-231 <= nums\[i\] <= 231 \- 1

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

## 2.思路 ##

（1）原地哈希

思路参考[本题官方题解][Link 1]。

## 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;
        }
    }

[Link 1]: https://leetcode.cn/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/