https://leetcode.com/problems/first-missing-positive/#/description
找到一个解法并不难，困难的是如何做到不用额外空间并且O(n)时间。根据要求来推算法的话，基本上就只能想办法利用问题本身的性质了。时间O(n)额外空间O(1)的算法一定是线性扫描，诸如线型DP, 快慢指针，bucket等等。
对于本问题，一个完美的数组应该长下面这个样子：
| 0 | 1 | 2 | ... | n-1 |
|---|---|---|---|---|
| 1 | 2 | 3 | ... | n |
其中上面一行是下标索引，下面一行是数组元素值。对于不是这样的数组，就想办法把它变成这样，幸运的是可以利用索引和值的关系快速地进行这样的转换——我们希望下标为i的位置对应的元素是i+1，或者将不在正确位置上的元素nums[i]放到位置nums[i]-1上（如果可以的话）。
具体地，扫描原数组：
- 如果
nums[i] <= 0或者nums[i]比数组的长度还大，不管它，继续； - 否则看它是否在正确的位置上，即是否满足
nums[i] = i + 1，如果不满足就将它与nums[nums[i]-1]交换（如果可以成功交换，就循环做这一步，直到两个位置上的元素相等为止） - 最后，如果上面的动作都没做过，说明我们遇到了一个完美数组，返回
数组长度+1即可
class Solution { public:int firstMissingPositive(vector<int>& nums) {if (nums.empty()) {return 1;}for (int i = 0; i < nums.size(); ++i) {int eidx = nums[i] - 1;if (nums[i] > 0 && eidx < nums.size() && nums[i] != i+1 && nums[i] != nums[eidx]) {std::swap(nums[i], nums[eidx]);i--;}}for (int i = 0; i < nums.size(); ++i) {if (nums[i] - 1 != i) {return i + 1;}}return nums.size() + 1;} };