Given an unsorted integer array, find the first missing positive integer.
For example,Given [1,2,0] return 3,and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
本题现需要对数组进行排序，将如果当前的数超出了 1 到 n-1的范围，跳过。如果是1到n-1但是，A[i]不等于i+1，并且在 A[i] - 1 的位置的数不满足 A[A[i]-1]+1的要求，那就将两个位置的数置换。然后寻找到第一个A[i]!=i+1的位置，i+1就是消失的第一个正数。我本次偷换了排序算法，也通过了测试。时间：4ms。代码如下：
class Solution { public: int firstMissingPositive(vector<int>& nums) { sort(nums.begin(), nums.end()); int k = 1; for (size_t i = 0; i < nums.size(); ++i){ if (nums[i] == k) k++; else if (nums[i]>k) return k; } return k; } };
转载于:https://www.cnblogs.com/Scorpio989/p/4583675.html
