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了。

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

比如输入 -3　　1　　5　　3　　2

index　　0　　1　　2　　3　　4

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

i = 0:　　-3　　1　　5　　3　　2　　负值跳过了

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

i = 1:　　1　　-3　　5　　3　　2　　负值跳过

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

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

i = 2:　　1　　2　　-3　　3　　5　　负数跳过

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

i = 4:　　1　　2　　 3　　-3　　5　　负数跳过

最后变成了　　1　　2　　 3　　-3　　5

很明显，缺的是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 + ;

    }

};

巴特西

Leetcode 题解 First Missing Positive

最新文章

热门文章