leetcode41 缺失的第一个正数

一、问题描述

二、解题思路

由于本题要求时间复杂度为O(n)，空间复杂度为常数级，所以不能使用枚举和哈希表来解决，智能就地解决，可以用向量nums来模拟哈希表(原地哈希)，解题思路如下：

(1)首先，遍历向量nums，如果nums[i]>0且未在正确的位置上，就将其换到正确的位置上，注意不能越界，完成遍历，将所有正整数n放置到索引位置n-1；

(2)然后，遍历操作完后的nums向量，如果在遍历过程中发现nums[i]!=i+1，就返回i+1，这个数字即为缺失的数字；

若遍历完成仍未发现，就返回n+1，即为缺失的最小正数。

注意：交换到正确位置要用while，因为要保证换过来的数字也要换到正确的位置。

三、代码实现

class Solution { public: int firstMissingPositive(vector<int>& nums) { //将数字i放到i-1的位置上(i>0),然后再进行遍历寻找缺失的数字 int n=nums.size(); //将数字i放到i-1位置 for(int i=0;i!=nums.size();i++){ //注意：使用while，保证交换过来的数也能被放到正确的位置 while((nums[i]!=i+1)&&(nums[i]>0)&&(nums[i]<=n)) swap(nums[i],nums[nums[i]-1]); } //遍历寻找缺失的数字 for(int i=0;i!=nums.size();i++) if(nums[i]!=i+1) return i+1; return n+1; } };