力扣(LeetCode)41. 缺失的第一个正数(C++)

类计数排序

小于 $1$ ，大于 $n$ 的数，不会对答案造成影响。所以只要考虑 $1——n$ 的数。

由于题目要求 $O(1)$ 空间，参考计数排序思想，利用原数组 $nums$ 存储 $1——n$ ，需要将 $1——n$ 的下标映射到 $0——n-1$ ， 这一步等同于判断 $nums[i]$ 和 $i+1$ 是否相等。如果相等，说明 $i$ 存的数正确，如果不相等，将 $nums[i]$ 存到它该存的位置 ， 即减 $1$ 映射后的下标 $nums[i]-1$ 。

每一次交换会把一个数放在该放的位置，一次遍历，所有数的位置确定。最后从小到大，枚举每个位置是否存放相应的数，如果缺失，返回缺失值，即为所求。

提示 : 如果有重复元素，他们对应同一位置，造成死循环，在循环条件里一定要判重。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0;i<n;i++){
            while(nums[i]>0&&nums[i]<=n&&nums[i]!=i+1&&nums[i]!=nums[nums[i]-1])//&&nums[i]!=i+1 TLE 优化 nums[i]!=nums[nums[i]-1]
                swap(nums[i],nums[nums[i]-1]);
        }
        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

时间复杂度 $O(n)$ ， 一次遍历确定所有数的位置，时间复杂度 $O(n)$ ，枚举每个位置是否存放相应的数，时间复杂度 $O(n)$ 。总时间复杂度 $O(2\times n)$ ，忽略常数时间复杂度 $O(n)$ 。

空间复杂度 $O(1)$ ，只用到常量级额外空间。

致语

理解思路很重要！
欢迎读者在评论区留言，答主看到就会回复的。

AC