O(n)时间复杂度常数空间求解最小未出现正整数

LeetCode41

​ 这道题的难点在于，既要求时间复杂度控制在O(n)，有要求常数级空间复杂度。

​ 假设抛开时间复杂度复杂度这一要求，我们可以使用快排或者二分来实现，都能满足常数时间复杂度的要求。

​ 如果抛开空间复杂度这一要求，我们可以额外创建一个哈希表来记录数组中的数，能够满足O(n)时间复杂度的要求。

​ 如果想要满足这两个要求，这是一种思维上的挑战。这里的想法是，其实题目中有一个隐含条件，那就是[1,2,…n]这个数组，我们只要保证让n以内的数在nums中有序，再通过对比这个数组就能找出最小未出现正整数，这也是排序做法的思路。做法就是让这些数回到它们本应该在的位置，比如2应该在nums下标为1的位置，同理，n应该在nums下标为n-1的位置，遍历nums每个数，将n以内的数交换至对应的位置，这样就能实现nums数组的部分有序性，这样就既符合时间复杂度O(n)(交换的次数非常少),常数级空间复杂度。

​ 实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        for(int i = 0; i < n; i ++){
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]){
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
                //由于nums[i] - 1依赖于nums[i]因此以下这种交换规则是错误的，期间nums[i]已经改变了
                // int temp = nums[i];
                // nums[i] = nums[nums[i] - 1];
                // nums[nums[i] - 1] = temp;
            }
        }

        for(int i = 0; i < n; i ++){
            if(nums[i] != i + 1){
                return i + 1;
            }
        }
        return n + 1;
    }
}