化蝶去寻花
夜夜栖芳草
在评论里说看到一个词“原地哈希”，感觉非常贴切呀。。。做过类似的这种题不少了，很多时候规定常数的空间复杂度，我都会采用“标记为负数”等方式记录额外信息，感觉类似的方式都可以称作“原地哈希”。
这道题的话，如果允许用额外空间，那简直不要太简单，直接开个数组就完事，评论区也会看到类似这样的做法。作为参与互联网内卷的一颗韭菜苗，我由衷地希望这样的同学能够多一点，这样我面试可能轻松点2333。
讲岔了，说回题目。。。
其实整个数组中，小于等于0以及大于数组大小的元素值，对于解出 First Missing Positive 都属于无用信息，却占用了一定的内存空间，。
因为理论上，大小为size的数组刚好可以存下[1, size]的所有数，如果存不下，就存在无用信息。
所以需要做的就是如何找出并利用上无用信息。方法可以是这样：遍历数组，把每个元素移动回本来的位置，如果数组当前元素x满足0 < x <= size，且当前下标i与当前元素x不是x = i + 1或者nums[x - 1] == x的关系，则通过交换（x和nums[x-1]）的方式，直到能够将元素移动到本来的位置或者是找到了无用信息。
把数组中所有的元素经过这样的处理后，再从头遍历，就能发现，第一处记录无用信息的地方就是答案。。。
遍历完都不存在无用信息，答案就是size + 1。
代码中注意：
if nums[i] != nums[nums[i] - 1]
和
if nums[i] != i + 1
两种交换判断的区别是，前者可以规避掉重复元素的情况，而后者不行。
完整代码如下：
class Solution {
public:
int firstMissingPositive(vector<int> &nums) {
int size = nums.size();
for (int i = 0; i < nums.size(); i++) {
while (0 < nums[i] && nums[i] <= size && nums[i] != nums[nums[i] - 1])
std::swap(nums[i], nums[nums[i] - 1]);
}
for (int i = 0; i < size; i++) {
if (i + 1 != nums[i])
return i + 1;
}
return size + 1;
}
};
