【First Missing Positive】cpp

题目：

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.

代码：

class Solution {

public:

    int firstMissingPositive(vector<int>& nums) {

            const int len = nums.size();

            for ( int i = ; i < len; ++i )

            {

                while ( nums[i]!=i+ )

                {

                    if ( nums[i]>len || nums[i]< || nums[i]==nums[nums[i]-] ) break;

                    std::swap(nums[i], nums[nums[i]-]);

                }

            }

            for ( int i = ; i < len; ++i )

            {

                if ( nums[i]!=i+)

                    return i+;

            }

            return len+;

    }

};

tips：

通过此题学习了桶排序（bucket sort）

桶排序原理讲解 http://bubkoo.com/2014/01/15/sort-algorithm/bucket-sort/

桶排序演示动画 http://www.cs.usfca.edu/~galles/visualization/BucketSort.html

大神的解答 http://fisherlei.blogspot.sg/2012/12/leetcode-first-missing-positive.html

自己coding的时候思考过程如下：

1. 此题设计的是最简单的桶，利用nums[i]存放i+1

2. 如果某个位置上nums[i]不等于i+1，则就swap(nums[i], nums[nums[i]-1])

　为什么是这样的？因为nums[i]=i+1→nums[i]-1=i→nums[nums[i]-1]=i，简单说就是把nums[i]这个值放到它该放到的桶里面。

3. 紧接着考虑2中swap能成每次都立么？显然不能：nums[i]>len nums[i]<1这两个条件出现时已经超出了nums数组量程。显然是不行的。

还有一种隐蔽的情况也是不能swap的，比如[1,1]会陷入死循环，因此在swap之前还需要判断nums[i] != nums[nums[i]-1]。

4. 把1~3的过程走完，再遍历数组nums，判断nums[i]!=i+1第一次出现的位置。

5. 如果4中把nums都走过一遍，也没有发现缺失的，则证明缺失的是len+1。

=============================================

第二次过这道题，直接记住思路了，默写了一遍。

class Solution {

public:

    int firstMissingPositive(vector<int>& nums) {

            for ( int i=; i<nums.size(); ++i )

            {

                while ( nums[i]!=i+ )

                {

                    if ( nums[i]>nums.size() || nums[i]< || nums[i]==nums[nums[i]-] ) break;

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

                }

            }

            for ( int i=; i<nums.size(); ++i )

            {

                if ( nums[i]!=i+ ) { return i+; }

            }

            return nums.size()+;

    }

};

巴特西

【First Missing Positive】cpp

最新文章

热门文章