LeetCode--41.缺失的第一个正数

前言：暑假开始咯，可以好好更新了，可以好好期待一下哦

解题思路：

        1.获取信息：

                给定一个未排序的整数数组，要求找出没有出现的最小正数

                限制条件：时间复杂度为O(N)，只能使用常数级别的额外空间

                提示：1 <= nums.length <= 105

       -pow(2,31) <= nums[i] <= pow(2,31) - 1

        2.分析题目：

                （我做了，发现题目中其实没有标明一些额外的信息，这些信息要你去做，然后碰壁之后，才会发现，所以人生就是一个碰壁然后不断学习的过程，在这里我就直接写出来了）

                额外信息：数组中会有重复的元素

                我一开始，看到这个限制条件，本来想像之前一样，出个反骨法的，但是如果无视只能使用常数级别的额外空间这个条件时，我想到会用一个较大的容器来装入每个数字，之后进行遍历，看看哪个最小的正整数的不在其中即可，但是由于数字最大可为INT_MAX，如果无视这个条件的话，分配这个大个空间，时间复杂度早就不堪重负了

                所以，本次题解没有喜闻乐道的反骨法（即，哈希表法），那就老老实实开始解题吧

                我把每种方法的思路放在了尝试编写代码环节里面，借着代码来帮助你理解，这里就不做过多的阐述了

        3.示例查验：

                示例2：提醒你，数组中还会出现负数和0

                示例1和示例3：留着试验自己的思路是否可行

        4.尝试编写代码：

                （1）动态规划：

                        思路：既然无序实在是难以下手，那么不如就把它排序一下

                                我们把它排序过后，从左往右开始遍历

                                由于要寻找未出现的最小正整数，所以，负数和0都跳过，即：舍去，不考虑

                                接下来就全是正整数了

                                此时无非就三种情况：

                                1.第一个正整数不为1，说明，最小的未出现的正整数为1

                                2.第一个正整数为1，且后续的正整数都是连续的，说明，未出现的正整数为该数组内最大的正整数加上1

                                3.第一个正整数为1，但后续的正整数不连续，说明，最小的正整数在这些正整数的中间（不包括第一个正整数和最后一个正整数）

以下是完整代码：

class Solution {
public:int firstMissingPositive(vector<int>& nums) {sort(nums.begin(),nums.end());//对数组进行从小到大的排序int size=nums.size();//求出数组的大小if(nums[size-1]<=0)return 1;//如果排序后的数组中最大的数小于1，则最小的未出现的正整数为1int pointer=0;//设立遍历的开头while(nums[pointer]<=0)pointer++;//跳过所有非正整数if(nums[pointer]!=1)return 1;//如果第一个正整数不为1，则返回1for(pointer;pointer<size-1;pointer++){//开始遍历if(nums[pointer+1]-nums[pointer]<=1)continue;//如果前一个正整数和后一个正整数等于或者两者相差1，则跳过else return nums[pointer]+1;//否则返回未出现的最小整数}return nums[pointer]+1;//返回数组中最大正整数加1}
};

                （2）分治法

                        思路：我们还是对它进行从小到大的排序

                        我们每次都将数组分为两部分，直到分成的小组中的数字为1或者2，这个时候，就可以轻而易举地得出，每个小组中未出现的最小正整数是多少了，接下来就对这些正整数进行分析即可

                        话语无力，还是代码比较有说服了，这次要使用递归

以下是完整代码

class Solution {
public:int firstMissingPositive(vector<int>& nums) {sort(nums.begin(),nums.end());//排序int size=nums.size();//求出数组的大小if(nums[size-1]<=0)return 1;//如果排序后的数组中最大的元素小于1int begin=0;//设立左指针while(nums[begin]<=0)begin++;//跳过非正整数，确保指针指向的是第一个正整数if(nums[begin]!=1)return 1;//如果第一个正整数不等于1，则返回1return reBack(nums,begin,size-1,size-1);//开始进入递归}
private:int reBack(vector<int>&nums,int l,int r,int border){if(r-l<=1){//如果分成的小组中的元素数目为1或者2if(nums[r]-nums[l]>1)return nums[l]+1;//如果两个元素相差大于1if(r==border&&nums[r]!=INT_MAX)return nums[r]+1;//如果右边的元素的指针等于数组的边界且，右边的元素不等于INT_MAXreturn 0;都不是，则返回0，说明两个元素相等或者相差为1或者只存在一个元素}int mid=(l+r)/2;//求出中间的指针int left=reBack(nums,l,mid,border);//求出左边区间的未出现的最小正整数int right=reBack(nums,mid+1,r,border);//求出右边区间的未出现的最小正整数if(left==0&&right==0){//如果两边返回值都为0if(nums[mid+1]-nums[mid]>1)return nums[mid]+1;}else if(left!=0&&right!=0)return left<right?left:right;//略else if(left!=0&&right==0)return left;//略else if(left==0&&right!=0){//略if(nums[mid+1]-nums[mid]>1)return nums[mid]+1;return right;}return 0;}
};

                （3）拟哈希表法 I

                        思路：我们在前面说了为什么本道题没有写反骨法对吧，那我们可不可以用另一种形式来模仿一下反骨法呢？

                        当然可以，哈希表法的本质是一个容器中存有连续的数，将一个数组中的所有元素放入其中，可以清晰地看见哪几个数并不连续

                        还是看代码吧，我就不阐述了，等明天早上，我补充一个图片吧，应该就比较好理解了

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

                （4）拟哈希表法 II

                        思路：其实跟拟哈希表 I 方法差不多，所以，就看代码吧

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

本次题解就完事了，今天吃了一天的饭，很累了，但我还是坚持写完，有没有一点小小的感动

还是提一下，纸上得来终觉浅，绝知此事要躬行