LeetCode 41. First Missing Positive

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
Note:

Your algorithm should run in O(n) time and uses constant extra space.
解析：题目要求找到第一个缺失的正数，给一个没有排序的数组，找到第一个缺失的正数。比如给定[1,2,0]，则3为第一个缺失的正数；给定[3,4,-1,1],则第一个缺失的正数为2.同时要求时间复杂度为\(O(n)\)，并且需要常数的额外空间。
解法1:
如果不考虑额外的常数空间，则考虑采用一个set将数组中的所有元素存入，然后从1开始递增查找，看一下哪个数字不在。
代码如下：
[cc lang=”C++”]
class Solution {
public:
int firstMissingPositive(vector& nums) {
unordered_set nums_set;
int max_num = 0;
for(auto & item : nums)
{
if(item <= 0) continue; nums_set.insert(item); max_num = max(item, max_num); } for(int i=1; i < max_num; i++) { if(!nums_set.count(i)) return i; } return max_num + 1; } }; [/cc] LeetCode倒是也可以提交通过。 解法2: 采用原地覆盖法覆盖原有的数组，我们的思路是把1放在数组第一个位置nums[0]，2放在第二个位置nums[1]，即需要把nums[i]放在nums[nums[i] – 1]上，那么我们遍历整个数组，如果nums[i] != i + 1, 而nums[i]为整数且不大于n，另外nums[i]不等于nums[nums[i] – 1]的话，我们将两者位置调换，如果不满足上述条件直接跳过，最后我们再遍历一遍数组，如果对应位置上的数不正确则返回正确的数。
代码如下：
[cc lang=”C++”]
class Solution {
public:
int firstMissingPositive(vector& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) { while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { swap(nums[i], nums[nums[i] - 1]); } } for (int i = 0; i < n; ++i) { if (nums[i] != i + 1) return i + 1; } return n + 1; } }; [/cc]