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.

思路

注意时间复杂度和空间复杂度。因为是O(N)的时间复杂度，所以一般的排序算法行不通。

把出现的每个数通过hash记录，再从1开始遍历，看哪个没有，第一个没有的即为缺失的最小正整数。

hash这个不满足O(1)的空间复杂度

采用交换的方法：http://www.cnblogs.com/grandyang/p/4395963.html

c++11

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