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.
题意： 给定一个无序的序列，找到其中首次缺少的正数。
题目好抽象！！！lz表示这个题意看了老久才看明白！！！
题目有一个前提，如果是一个合法的序列，那么给定的一个长度为N的序列排序之后应该是[1,2,...,N-1,N]。这个前提很重要！！！
可是，现在序列中某些数字可能缺失：
例如长度为4的序列[3,4,-1,1]。 排序之后为[-1,1,3,4]。 那么首次缺失的数字为2.
这样看应该不直观，换个思路： 假设数组下标以1开始，那么将数组按照A[i]=i排列，那么可以得到序列[1,-1,3,4]。这样就能发现在A[2]!=2
-----------------------------------------------------------------------------------------------------------------------------
拿到这个题目思路：
（1）首先如果忽略时间和空间复杂度的限制，能够想到的方法，a. 排序 b.根据排序之后的序列依次查找1，2，..,n 直到第一个缺失的数字。 （易知排序后的查找问题的时间复杂度为O(N)）
（2）找到满足时间复杂度的做法： 由于前提长度为N的序列正确排列为[1,2,...,N-1,N]. 所以可以用桶排序，或者基数排序。时间复杂度为O(N). 但是，这些排序方法空间复杂度为O(N)..
（3）如何找到空间复杂度为O(1)的做法呢。
在组合数学里面有错排的概念，即由[1~N]组成的序列中存在 A[i] != i的情况。这和本题的意思比较接近。
那么，问题就变成了从乱序排列还原成正序最少需要多少次两两交换。 答案是O(N)。 此处证明省略。（好吧，其实lz也没想明白怎么证明 -。-！）
以下例子参考csdn一篇帖子： http://blog.csdn.net/famousdt/article/details/7301782
思路： 举个例子来说， 。我们让 i 从1开始判断是否在i是否在该在的位置上。此时i=1不在位置1上，而且位置1上是2。2应该放在位置2上，而位置2上是5。位置5上是1。这就说明1,,5三个数轮换一下，就能将这三个数换到各自应该在的位置。需要换2次。 顺着这个思路想，可以把1,,5看成一个环，,4看成另一个环。那么最后的答案就是 整个数列中不在各自该在位置的数的数量 - 环数。此例子中，就是5-= 所以，一个环中，如果有x个数，那么这个环需要x-1次操作。剩下的重点就是找出所有的环了。
根据以上分析可知，题目思路分为两步：
（1） 在O(N)时间内，将错排还原成正序。
（2） 从头开始查找第一个不符合 A[i]==i 的数字，即为所求结果。
例子：
A=[ ] n=4, i=1
-------------------------------------------
序列 3
-------------------------------------------
起始： A[1]=4 swap(A[1],A[4])
-------------------------------------------
-------------------------------------------
继续交换 A[1]=3 swap(A[1],A[3])
-------------------------------------------
-------------------------------------------
A[]=,不能继续交换 i++.
A[]=, 无需交换， i=i+, i=
A[]=, 无需交换， i=i+, i=
A[]=, 无需交换， i=i+, i=
退出。
最终的序列为 0 2 3 4
PS：在下面的代码中，数组的下标从0开始。
class Solution {
public:
int firstMissingPositive(int A[], int n) {
int i=;
while(i<n)
{
if(A[i]<= || A[i]>n || A[i] == i+) i++; // 无法继续进行交换
else
{
int target=A[i]-;
if(A[i]!=A[target]) swap(A[i],A[target]);
else i++;
}
}
i=;
while(A[i]==i+) i++;
return i+;
}
};
ok！终于搞定了。。。。
转载请注明出处： http://www.cnblogs.com/double-win/ 谢谢！