首页 > 其他 > 详细

leetcode 41. First Missing Positive

时间:2019-05-22 21:50:15      阅读:146      评论:0      收藏:0      [点我收藏+]

https://www.cnblogs.com/grandyang/p/4395963.html

https://www.jianshu.com/p/cf82ce91dc3d

 

错误解法1:

[1,1]的时候会死循环

这种写法,错误在nums[i] != i+1,这种写法不能解决出现两个相同数字的情况。nums[nums[i] - 1] != nums[i]的写法能解决如果index那个位置已经放好了满足要求的数,就可以退出循环。

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

 

错误解法2:

{3,4,-1,1}会错误

swap要一直循环。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for(int i = 0;i < nums.size();i++){
            if(nums[i] <= nums.size() && nums[i] > 0 && 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;
    }
};

 

正确解法:

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for(int i = 0;i < nums.size();i++){
            while(nums[i] <= nums.size() && nums[i] > 0 && 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;
    }
};
复杂度分析
虽然这个思想还是蛮好理解,但是在一个for循环里又出现了一个while循环,它的复杂度能是O(n)吗?其实是酱紫,算法复杂度应该看的是基本操作的次数,在这个问题里,基本操作指的是交换操作,而每次交换操作,都至少有一个数字去了它应该去的地方,那么一个n长度的数组,最多只需要n次交换操作,所以它的复杂度是O(n)的~

leetcode 41. First Missing Positive

原文:https://www.cnblogs.com/ymjyqsx/p/10908518.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!