当前位置：网站首页>LeetCode 41. Missing first positive number

LeetCode 41. Missing first positive number

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

41. First positive number missing
Insert picture description here
In situ Hash

class Solution {
    
public:
    int firstMissingPositive(vector<int>& nums) {
    
        
        int n = nums.size();
        for(int i = 0; i < n; i ++)
        {
    
            // In situ hash, Will be nums[i]  Put it in (nums[i] - 1) position 
            // Constantly changing positions , final nums[i] And i + 1 Unequal positions do not exist 
            
            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://yzsam.com/2022/04/202204221905153812.html

边栏推荐

猜你喜欢

随机推荐