LeetCode41 First Missing Positive 解题报告

By | 11/03/2018

[代码]:

#include<vector>

#include<iostream>

using namespace std;

class Solution {

public:

intfirstMissingPositive(vector<int>& nums) {

int n = nums.size();

if(n ==0){

return 1;

}

//第i位存放i+1数值

for (int i =0; i < n; i++)

{ //while部分相当的核心

while (nums[i]>0&& nums[i] < n && nums[nums[i]-1] !=nums[i])//num[i]-1对应意思就是本来数值的减去了1再去跟之前的标记交换 从而使得其满足下标i存的是i+1

swap(nums[nums[i]-1], nums[i]);

}

for (int i=0; i < n; i++)

{ //判断i对应的数值是不是比标签多一 如果满足要求那么通过 反之则将不满足要求的下表加1则是我们要找的数字因为满格是n-1

if (nums[i] != i +1)

return i +1;

} //如果都满足那么就是整体长度加1则是我们要找的最小整数

return n +1;

}

};

//以下为测试数据

int main(){

vector<int> p;

p.push_back(1);

p.push_back(2);

p.push_back(0);

Solution S;

S.firstMissingPositive(p);

}

 

【遇到的问题及解决办法】:

首先这一题的难度在于题目规定了我们只允许用O(n)的时间复杂度并且使用常量的时间来解决这一个题目,所以不能释放暴力的进行搜索,例如把所有的元素都进行比较并且便利一遍,并且可能是在有一定的算法思维了之后,我就是很浅显的觉得这个算法里面肯定只能有一层for循环绝对是不可以有两层嵌套的,故如果说我先把每个元素按照一定的规则安排好了之后再按照之前规定的原则进行遍历如果说遍历的这个元素不符合我们所规定的那么这个元素可能就是有问题的那么找出来再进行处理,但是如果所有的元素都是符合规定的那么遍历完了也好进行对应的处理,所以很显然我们的思路渐渐的出来了,对于排序算法熟悉的同学那么这个时候肯定就能想到桶排序,桶排序的过程类似这样:空桶[ 待排数组[ 0 ] ] = 待排数组[ 0 ];其实就是把数字和储存其数组的下标绑定在一起那么当我们找到数字下标的时候就是其本身了,有人可能会问为什么数字6不放在下标为5的数组中,你484傻还有元素0啊,你这样站位就相当于0下标放的就是1了那么我们万能的0放在哪里呢?好了,到了这个地方就又会有人问了,那为什么既然这样了我在此处需要把对数组中元素筛选的规则设置为数字i+1对应的是下标i为什么在这个地方我们考虑到0呢?这个时候请让我们一起看代码再最开始的部分对于空数组就是返回的1然后最后的如果全部都是符合筛选规则的话那么就是再i的基础上加一返回那么如果就算0没有排进去有算得了什么呢,比如有0,2,1,那么根据此处设定的规则a[0] = 1; a[1] = 2;假设有元素的索引为-1;a[-1]=0,所以遍历完了,发现i = 2的地方不对劲那么就是i+1同理如果全部都是对的那么就是当前的下标n+1因为之前存的元素比下标大一嘛。

如果你觉得我的文章不错,欢迎打赏:

WechatIMG47

发表评论