41. 缺失的第一个正数

题目链接：https://leetcode.cn/problems/first-missing-positive/description/

 

 

 

 

 

 

 

 

 

 

解析：

这道题蛮有意思的，隐含了一个条件，要找的数一定在[1, N + 1]之间，所以就将大于0且小于等于N的数放到相应的下标位置

最后遍历哪个位置不符合就好了

 

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