[LeetCode]First Missing Positive

要求constant space，不能用数据结构存之前的数据从而不断更新结果。所以我们尝试操作原数组，假设数组size为n，我们只要把正整数i放在index为i - 1的地方，就相当于用map标记了这个数出现过，之后我们从左往右扫第一个不match的数就是我们要的答案。要达成这个目的我们只需要确定i的数在[1,n]的范围，nums[i] != i + 1的情况下，每次把nums[i]和nums[nums[i]]的数交换，注意如果两者相等就别换了，会陷入无限循环，这样只要数组充存在[1,n]的数，它就会被换到所在的位置。时间复杂第O(n)，常数空间，代码如下：

	class Solution {
	public:
	int firstMissingPositive(vector<int>& nums) {
	int len = nums.size();
	for(int i = 0; i < len; ++i)
	{
	while(i != nums[i] - 1)
	{
	if(nums[i] >= 1 && nums[i] <= len && nums[i] != nums[nums[i] - 1] )
	swap(nums[i], nums[nums[i] - 1]);
	else
	break;
	}
	}
	for(int i = 0; i < len; ++i)
	if(i != nums[i] - 1)
	return i + 1;
	return len + 1;
	}
	};

view raw First Missing Positive.cpp hosted with ❤ by GitHub

这道题的做法可以给我们其他的题一些思路，当input的范围在一个连续的区间且区间长度和input数组长度接近时，我们可以modify原数组来当做一个map。