leetcode_41. First Missing Positive_cyclic swapping

https://leetcode.com/problems/first-missing-positive/

给定一个长度为len的无序数组nums,找到其第一个丢失的正整数。

解法:

使用cyclic swapping algorithm。将满足条件  0 < num <= nums.size()的num放到下标为num的位置上,最终第一个nums[i]!=i的i即是最小的丢失的正整数。

代码将num放在下标为num-1的位置,思想是一样的。

注意交换的条件,避免死循环。

class Solution
{
public:
    int firstMissingPositive(vector<int>& nums)
    {
        int res=0;
        for(int i=0; i<nums.size(); i++)
            while(nums[i]>0 && nums[i]<=nums.size() && nums[i]!=i+1 && nums[nums[i]-1]!=nums[i])
                swap(nums[i], nums[nums[i]-1]);
        for(int i=0;i<nums.size();i++)
            if(nums[i]!=i+1)
                return i+1;
        return nums.size()+1;
    }
};

 

leetcode_41. First Missing Positive_cyclic swapping

上一篇:[luaj]在安卓用使用luaj


下一篇:java 反射