Leetcode 题解 First Missing Positive

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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)时间，而且是o(1)空间。

一开始想的是记录正数的个数和他们的和，利用1~n的公式求和，减去sum，看缺了哪个。

指导提交错误，发现居然可以输入 [1,1]。原来还可以有重复的。

想到应该是利用了原来的数组。

用原来的数组做哈希。

对于每一个数，把它放到它应该在的位置上。比如一个4，把它放到a[3]的位置上。

原来的数怎么办呢？调换。a[3]原来的数就放在a[i]的位置。反复调换，反复调换。当然其中有坑的，我提交了三次才AC了。

下面代码的执行效果就是：

比如输入 -31532

index01234

————————————————

i = 0:-31532负值跳过了

i = 1:1-3532swap(-3,1)

i = 1:1-3532负值跳过

i = 2:1-33swap(5,2)

i = 2:12-335swap(2,-3)

i = 2:12-335负数跳过

i = 3:12 3-35swap(-3,3)

i = 4:12 3-35负数跳过

最后变成了 12 3-35

很明显，缺的是4啦。

class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int i,j,n,tmp;
vector<int> &a = nums;
n = a.size(); if(n == ) return ; for(i = ,j = ; i < n; i++)
{
if(a[i] > && a[i] != i + )//一个正数不在它自己的位置上，
{
tmp = a[i] - ;//tmp是它应该呆的位置
if(tmp < n && a[tmp]!= a[i])//防止下标越界和死循环
{
swap(a[tmp],a[i]);
i--;
}//这个调换最多会有多少次呢？最多也就是n次。因为n次以后，n个数都会在正确的位置了。
}
}
for(i = ; i<n; i++)//数一数，看看中间却了哪个呢？如果都不缺，那就是1..n的连续数组，就返回 n + 1
{
if(a[i] != i + )
break;
} return i + ;
}
};