Leetcode-First Missing Positive

http://oj.leetcode.com/problems/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.

思路

假设数组长度是n。那么第一个missing的正数肯定不会超过n。

如果把所有正数都放在正确的位置上,数字1(如果有的话)在A[0], 数字2(如果有的话)在A[1]数字i + 1在A[i],那么我们只要扫描A,遇到第一个A[i]不等于i+1的,就知道这个missing的正数(i+1)了。

具体方法是,扫描数组A,如果当前的正数A[i]不在其该在的位置,那和A[A[i]-1]交换(这样交换过后A[i]-1的正数就in postion了。继续,直到i位置上的正数是正确的。然后继续下一个交换。

这样总能把所有正数in position。

AC代码

#include <iostream>
#include <cstdio>

using namespace std;

int firstMissingPositive(int A[], int n)
{
        for(int i = 0; i < n; i++)
        {
            int cur = A[i];
            while(cur >= 1 && cur <= n && A[cur-1] != cur)
            {
                int temp = A[cur -1];
                A[cur - 1] = cur;
                cur = temp;
            }
        }

        int j;
        for(j = 0; j < n; j++)
        {
            if(A[j] != j + 1)
                break;
        }
        return j + 1;

}

int main()
{
        int n;
        cin>>n;
        int A[n];
        for(int i = 0; i < n; i++)
            cin>>A[i];
        cout<<firstMissingPositive(A,n)<<endl;
        return 0;
}