leetcode - 41. First Missing Positive - Hard

descrition

Given an unsorted integer array, find the first missing positive integer.

For example,

Given [1,2,0] return 3,

and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

解析

注意题目的要求，时间复杂度： O(n)。如果没有时间复杂度的现在，我们可以对数组进行排序，并检查顺序数组中 positive 数的缺失情况即可，时间复杂度为O(nlog(n))。

在有时间复杂度限制的情况下，我们需要进一步分析题目的特点。

• 此处还需要注意的是，positive 是指那些大于 0 的数。
• 要找到第一个缺失的正整数（所谓的第一个正整数，是指从 1 开始计数，第一个缺失的正整数）

基本原理：对于 k 个正整数（允许重复），第一个缺失的值必然在区间 [1,k+1] 内。可以想象成，将 k 个球放到 k+1 个箱子里，那么必然有至少有一个箱子是空的。

对于长度为 n 的整型数组 arry[]，假设正整数的个数为 k 个，k<=n，那么缺失的值必然在区间 [1,k+1]内，我们可以将区间映射到 [0,k]（当 k=n 时，区间为[0,n-1]）。

（辅助理解：[1,k+1] 可以看成是从 1 开始顺序编号的箱子，直到 k+1，我们现在有 k 个正整数，正整数的数值表示起要放到几号桶，因为我们最多只有 k 个正整数，那么必然至少有一个桶时空的）

根据以上分析，对于任意正整数 1<=arry[i]<=n，我们可以从左边到右（从编号1开始到k）将其放到 arry[i]-1 的位置。满足 1<=arry[i]<=n 条件的数最多有 n 个。最后检查，如果存在 arry[i] != i+1 ，那么 i+1 就是缺失的第一个正整数，最极端的情况是 n 个数都满足 arry[i] == i+1，此时第一个缺失的正整数为 n + 1。（注意！！从左往右遍历）

具体实现如代码所示。注意，满足 1<=arry[i]<=n 条件的正整数有可能存在重复，因此需要检查即将要放置的目标位置是否已经满足条件，如果不满足条件才能放置。

code

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

class Solution{

public:

	// time-O(n), space-O(1)

	int firstMissingPositive(vector<int>& nums){

		int n = nums.size();

		// put the element to the right place

		// i must be increased from 0 to n, becasue we need to satisfy the lower number first

		for(int i=0; i<n; i++){

			while(nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i]){

				// note: nums[nums[i]-1] != nums[i] indicate the place nums[nums[i]-1] hasn't satisfied

				// so we can place the nums[i] to nums[nums[i]-1]

				swap(nums[i], nums[nums[i]-1]);

			}

		}

		// find the first missing positive

		for(int i=0; i<n; i++){

			if(nums[i] != (i+1))

				return i+1;

		}

		return n + 1;

	}

};

int main()

{

	return 0;

}