from CodeTop, Leetcode, 41. 缺失的第一个正数。
原地哈希。
题意：
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。示例 1：
输入：nums = [1,2,0]
输出：3示例 2：
输入：nums = [3,4,-1,1]
输出：2示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解读：
使用原地哈希方法，也即，数组本身当做哈希表，不需开辟额外空间。具体思想是，使数组第 i （下标，从 0 开始）个元素存储 i+1 （值），存储结束后，遍历哈希表，第一个 nums[i] != i+1 的位置，就是缺失的第一个正整数。具体做法是：
遍历数组，如果有 nums[i] != i+1，进 while 循环执行：第 i 个位置的值和第 nums[i] - 1位置的值交换，也就是让 nums[i] - 1 位置存放 nums[i] 这个值。注意，一定是交换，而不能直接赋值 nums[i] = i+1，因为 i + 1 这个值不一定在数组中存在。while 循环直到值不再合法而结束。值不在合法的意思是指：nums[i] 小于等于零或者大于数组长度，因为数组若存储正整数，最小存储 1 ，最大能存储到数组长度。或者，另一种退出情况是，nums[i]-1 这个位置，已经存储了 nums[i] 这个值，此时显然不能再交换了，也要退出。
代码：
for (int i = 0; i < nums.size(); i++){
while(nums[i] != i+1){
if (nums[i] <= 0 || nums[i] > nums.size() ||
nums[nums[i] - 1] == nums[i])
break;
int idx = nums[i] - 1;
nums[i] = nums[idx];
// 这一步目的不是给 i 位置赋值，而是给 nums[i] - 1 位置赋值
// 而 i 位置只是接收一下，或者说临时转储一下 nums[i]-1 位置的值
nums[idx] = idx++;
}
for (int i = 0; i < nums.size(); i++)
if (nums[i] != i+1) return i+1;
return nums.size()+1;// 如果前面都有，那缺失的第一个值一定是 nums.size()+1
}
