LeetCode41 缺失的第一个正数

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

第一种方法，置换，把每个x放到x-1的位置上（减一是因为这里是说正整数，如果不减一会没法处理到0号位置的数）。这样做完之后重新遍历，第一个不等于位置x+1的数就是答案。

 1 class Solution {
 2 public:
 3     int firstMissingPositive(vector<int>& nums) {
 4         int n = nums.size();
 5         for (int i = 0; i < n; ++i) {
 6             while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
 7                 swap(nums[nums[i] - 1], nums[i]);
 8             }
 9         }
10         for (int i = 0; i < n; ++i) {
11             if (nums[i] != i + 1) {
12                 return i + 1;
13             }
14         }
15         return n + 1;
16     }
17 };
18 
19 作者：LeetCode-Solution
20 链接：https://leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
21 来源：力扣（LeetCode）
22 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

第二种，原地哈希。哈希表可以直接处理这个问题，但是需要O(n)的额外空间。我们可以直接原地建立哈希表。因为答案只可能在(1,n+1)的范围内，所以可以原地哈希。先把所有非正数变为n+1，然后遍历数组，遇到任何一个小于n+1的数，假如为x，就把x-1的位置的数置为负的。操作完毕后最后遍历数组，遇到的第一个不是负数的位置x，就返回x+1。如果没有就返回n+1。

需要注意在第二次遍历的时候，判断出数字不是n+1后，应该把数组先取出来取绝对值，否则会造成访问负数位置，导致越界。

 1 class Solution {
 2 public:
 3     int firstMissingPositive(vector<int>& nums) {
 4         int n = nums.size();
 5         if (!n)
 6             return 1;
 7         for (int i = 0; i < n; ++i)
 8             if (nums[i] <= 0)
 9                 nums[i] = n+1;
10 
11         for (int i = 0; i < n; ++i) {
12             if (abs(nums[i]) != n+1) {
13                 int tempnum=abs(nums[i]);
14                 if (tempnum - 1 < n && nums[tempnum - 1] > 0)
15                     nums[tempnum - 1] = -nums[tempnum - 1];
16             }
17         }
18         for (int i = 0; i < n; ++i) {
19             if (nums[i] > 0)
20                 return i + 1;
21         }
22         return n+1;
23     }
24 };