【LeetCode】41. The first missing positive number

41、 缺失的第一个正数

题目：
给你一个未排序的整数数组 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

解题思路：

(原地哈希） O(n)

对于一个长度为 n 的数组,其中没有出现的最小正整数只能在[1, n + 1]中.这是因为如果[1, n] 都出现了,那么答案是 n + 1,否则答案是[1, n]中没有出现的最小正整数.

时间复杂度分析：

Although it seems to be a two-layer loop,But the innermostwhile循环,每循环一次,A number will be placed in the correct position,所以总共最多执行 n 次,因此总的时间复杂度为 O(n）

空间复杂度分析：No extra arrays are used,因此空间复杂度为O(1).

参考代码：

class Solution {
    
    public int firstMissingPositive(int[] nums) {
    
        int n = nums.length;
        for(int i = 0; i < n; i++){
    
            while(nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
    
                 int temp = nums[nums[i] - 1];
                 nums[nums[i] - 1] = nums[i];
                 nums[i] = temp;
            }
        }
        for(int i = 0; i < n ; i++)
            if( nums[i] != i + 1)
                return i + 1;
        return n + 1;  
    }
}