leetcode41. 缺失的第一个正数

1、题目

https://leetcode-cn.com/problems/first-missing-positive/

2、题意

题解1：set

class Solution { public: int firstMissingPositive(vector<int>& nums) { int res = 1; unordered_set<int> hash; for(auto x:nums) hash.insert(x); while(hash.count(res)) res++; return res; } };

题解2:题目要求空间复杂度为常数 所以不能用set 先将nums[i]每个>=0的数减1,可以构成的正数从0开始 ; 便利一遍nums数组 若nums[i]放到nums[nums[i]]的位置即可;

class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); if(!n) return 1; for(auto &x:nums) if(x>=0) x--; for(int i=0;i<n;i++) { while((nums[i]>=0&&nums[i]<n)&&i!=nums[i]&&nums[i]!=nums[nums[i]])//nums[i]在可以交换的最大范围内 并且i!=nums[i] nums[i]的nums[nums[i]]不相等（相等的话说明又重复元素） swap(nums[i],nums[nums[i]]); } for(int i=0;i<n;i++) if(nums[i]!=i) return i+1; return n+1; } };