【LeetCode】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
2

提示：

1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1

解题思路：

(原地哈希） O(n)

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

时间复杂度分析：

虽然看起来是是两层循环，但是最内层的while循环，每循环一次，就会将一个数放在正确的位置上，所以总共最多执行 n 次，因此总的时间复杂度为 O(n）

空间复杂度分析：没有用到额外的数组，因此空间复杂度为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;  
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16