41 First Missing Positive

题目

41 First Missing Positive/

题解

题目要求找到输入数组中未出现的最小正整数，同时要求：

1. 时间复杂度为O(n)
2. 只使用O(1)的额外空间

针对要求1，很容易想到使用计数排序的方法：开辟一个大小为K的计数数组（K为输入数据的范围大小），对输入数组进行计数排序，对排序后的数组从小到大进行扫描，即可找到未出现的最小正整数。

基于上述思路还能进一步优化：不进行排序，而且只对正整数进行计数。从左到右对计数数组进行扫描，当计数为0时返回当前下标（计数为0代表该正整数没有出现在输入数组），或者在扫描结束后返回下标加一（此时有两种情况：一、输入数组中没有出现正整数，此时返回值等于0+1；二、输入数组中的正整数包含了从1到最大值的所有正整数，此时返回值等于最大值+1）。

但是上述方法均不满足只使用O(1)的额外空间的要求2。为了满足要求2，我们需要充分利用输入数组本身。记输入数组为A，其大小为N，而A中未出现的最小正整数必然在区间[1,N+1]内，这意味着我们利用A本身对落在区间[1,N]内的正整数进行计数操作即可得出结果。

但是，直接写入计数值会造成数组信息丢失，为了保留数组信息我们只能进行交换操作。注意到，对于区间[1,N]内的一个正整数num，记它的计数值为C[num]，我们只需要区分两种情况，即C[num]是等于0还是大于0，因此计数值的具体数值是不必要的，我们只需要一个能够区分这两种情况的标记就行了。当出现num时，一个合理的标记是使得A[num-1]=num，而这仅通过交换也能够做到。为了标记所有[1,N]内的正整数，需要对数组A从左到右不停通过交换操作对下标i上的数字进行标记直到：①i不满足1 <= A[i] <= N，或者②位置A[i]-1已被标记好。

在上述循环操作结束后，从左向右扫描A，在标记不成立，也就是A[num-1]不等于num时返回下标加一，或者在扫描结束后返回下标加一，就能得出所求结果。

代码

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
	int firstMissingPositive(vector<int>& nums) {
		int total = nums.size();
		if (total == 0) {
			return 1;
		}

		int i;
		for (i = 0; i < total; ++i) {
			while (nums[i] > 0 && nums[i] <= total
					&& nums[i] != nums[nums[i] - 1]) {
				swap(nums[i], nums[nums[i] - 1]);
			}
		}

		for (i = 0; i < total; ++i) {
			if (nums[i] != i + 1) {
				break;
			}
		}

		return i + 1;
	}
};