Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0] Output: 3
Example 2:
Input: [3,4,-1,1] Output: 2
Example 3:
Input: [7,8,9,11,12] Output: 1
Follow up:
Your algorithm should run in O(n) time and uses constant extra space.
class Solution { public: int firstMissingPositive(vector<int>& nums) { //遍历一遍，将所有的小于n的正数放到对应的位置 int n = nums.size(); for(int i=0;i<n;){ if(nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i]-1]){ swap(nums[i],nums[nums[i]-1]); }else{ i++; } } //寻找第一个不符合要求的正整数 for(int i=0;i<n;i++){ if(nums[i] != i+1) return i+1; } return n+1; } };
原文：https://www.cnblogs.com/wsw-seu/p/13661927.html