当前位置：网站首页>LeetCode 41. 缺失的第一个正数

LeetCode 41. 缺失的第一个正数

2022-04-22 19:05:00 【HumbleFool】

41. 缺失的第一个正数
在这里插入图片描述
原地Hash

class Solution {
    
public:
    int firstMissingPositive(vector<int>& nums) {
    
        
        int n = nums.size();
        for(int i = 0; i < n; i ++)
        {
    
            //原地hash，就是将nums[i] 放到(nums[i] - 1)位置上
            //不断的交换位置，最后得到的nums[i]与i + 1不相等的位置就是不存在的
            
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
                swap(nums[nums[i] - 1], nums[i]);
        }
        
        for(int i = 0; i < n; i ++)
            if(nums[i] != i + 1)
                return i + 1;
        return n + 1;
    }
};

版权声明
本文为[HumbleFool]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_45925322/article/details/124340097

边栏推荐

猜你喜欢

随机推荐