给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例1:
输入: [1,2,0]
输出: 3
示例2:
输入: [3,4,-1,1]
输出: 2
示例3:
输入: [7,8,9,11,12]
输出: 1
提示：
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
//
// Created by tannzh on 2020/7/6.
//
/*
*
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例1:
输入: [1,2,0]
输出: 3
示例2:
输入: [3,4,-1,1]
输出: 2
示例3:
输入: [7,8,9,11,12]
输出: 1
提示：
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
*/
#include <iostream>
#include <vector>
using std::vector;
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
auto n = nums.size();
for (int i=0; i<n; i)
while (nums[i]>0 && nums[i]<=n && nums[i]!=nums[nums[i]-1])
std::swap(nums[i], nums[nums[i]-1]);
for (int i=0; i<n; i)
if (nums[i] != i 1) return i 1;
return n 1;
}
};
int main(int argc, char **argv)
{
std::vector<int> nums1 = {1,2,0};
std::vector<int> nums2 = {3,4,-1,1};
std::vector<int> nums3 = {7,8,9,11,12};
Solution s;
std::cout << s.firstMissingPositive(nums1) << std::endl;
std::cout << s.firstMissingPositive(nums2) << std::endl;
std::cout << s.firstMissingPositive(nums3) << std::endl;
return 0;
}
这道题，能把题意看明白，就很不容易了。
1,2,0 -> 0,1,2,3 -> size == 3
^
3,4,-1,1 -> -1,1,2,3,4 -> size == 4
^
按照上述排列方式，就能很清晰的看出，First Missing Positive 的含义。这个数有如下几个条件：
- 最大为 n 1. (想象第一个例子，极端情况为 1,2,3, 那么 result 即为 4, 恰为 n 1)
- 最小为 1.
- 1 ~ n 1 中间，第一个缺的数，即为返回结果。(容易理解，如果 1~n 都没有缺的，那么结果一定是 n 1 了)
所以问题来了，怎么能在一次迭代中找出缺的那个？想象我们大脑是如何一下子看出来的？嗯，排列。
但排列完，就已经耗费了 O(N)，又要花 O(N) 去确认缺的那个数。其实，我们真的是排完序才知道空缺吗？显然不是。
另外，这道题要求不能用额外的空间，即使往排序上想，也只能想着如何 swap 了。
一般的排序，的确是比较复杂的。但仔细观察这道题，能够发现这个"排序"却比较特殊，首先它是从 1 开始的，且连续。
这让我们想到了神马？没错，像序号，就如数据库表的自增主键一样！那么找到缺的，岂不是一眼就看出来了？
如何能让这个无序的数组，看起来像序号一样呢？而且手段只有 swap. 有了，序号我们是知道的啊，这样 swap 就有明确的目的了。
index: 1, 2, 3, 4
array: 3, 4,-1, 1
^ ^ --- swap(3,-1)
-1, 4, 3, 1
^ ^ --- swap(4, 1)
-1, 1, 3, 4
^ ^ --- swap(1,-1)
1,-1, 3, 4
^
经过几步 swap, 我们惊人的发现最终对不齐的那个序号（2 : -1）就是我们要的结果！我们尝试用代码描述上述过程：
for (int i=0; i<n; i)
while (A[i]>0 && A[i]<=n && A[i]!=A[A[i]-1]) // 前两个条件限定范围，最后是如果序号位置的值与当前值一样，交换无意义
swap(A[i], A[A[i]-1]);
for (int i=0; i<n; i)
if (A[i] != i 1) return i 1; // 最后的检查，一旦发现与序号不符，立刻返回
return n 1; // 如果都相符，那么返回 n 1
6行，提交，最高效率 AC.(4ms)
,
