leetcode41 缺失的第一个正数

一、问题描述二、解题思路由于本题要求时间复杂度为O(n)空间复杂度为常数级所以不能使用枚举和哈希表来解决智能就地解决可以用向量nums来模拟哈希表(原地哈希)解题思路如下(1)首先遍历向量nums如果nums[i]0且未在正确的位置上就将其换到正确的位置上注意不能越界完成遍历将所有正整数n放置到索引位置n-1(2)然后遍历操作完后的nums向量如果在遍历过程中发现nums[i]!i1就返回i1这个数字即为缺失的数字若遍历完成仍未发现就返回n1即为缺失的最小正数。注意交换到正确位置要用while因为要保证换过来的数字也要换到正确的位置。三、代码实现class Solution { public: int firstMissingPositive(vectorint nums) { //将数字i放到i-1的位置上(i0),然后再进行遍历寻找缺失的数字 int nnums.size(); //将数字i放到i-1位置 for(int i0;i!nums.size();i){ //注意使用while保证交换过来的数也能被放到正确的位置 while((nums[i]!i1)(nums[i]0)(nums[i]n)) swap(nums[i],nums[nums[i]-1]); } //遍历寻找缺失的数字 for(int i0;i!nums.size();i) if(nums[i]!i1) return i1; return n1; } };