first-missing-positive

题目描述

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

题解

数值信息转移到位置信息上

int firstMissingPositive(vector<int>& nums) {
	int pos = 0;
	int len = nums.size();
	//第一趟，清理0和负数
	while (pos < len)
	{
		if (nums[pos] <= 0)
			nums[pos] = len + 2;
		++pos;
	}
	//第二趟，处理绝对值在1-len之间的数字。（在处理过程中会再次出现负数）
	pos = 0;
	while (pos < len)
	{
		int t = abs(nums[pos]);
		if (t<=len)
			nums[t - 1] = -abs(nums[t - 1]);//用负号表示pos+1已经出现过
		++pos;
	}
	//数值信息转移到位置信息上
	//第三趟，找到第一个还是正数的位置pos，返回pos+1
	pos = 0;
	while (pos < len)
	{
		if (nums[pos]>0)
			return pos + 1;
		++pos;
	}
	return len + 1;
}

若没有时间的限制，可以直接排序后遍历查找。

若没有空间的限制，可以创建辅助空间后记录。