程序员人生网站导航

LeetCode First Missing Positive

栏目：php教程时间：2015-03-09 09:04:25

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,⑴,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

题意：找到第1个最小的正整数。

思路：由于要求不能用到额外的空间，题目有暗示：答案在[1,n+1]之间。每一个位置都试着将这个位置的值换到对应的下标，这样第1个位置出现不是相应的值的时候就是答案，还有就是要是都能对应，那末n+1就是解

class Solution { public: int firstMissingPositive(int A[], int n) { for (int i = 0; i < n; i++) A[i]--; for (int i = 0; i < n; i++) { while (A[i] != i && A[i] >= 0 && A[i] < n) { if (A[i] == A[A[i]]) break; swap(A[i], A[A[i]]); } } for (int i = 0; i < n; i++) if (A[i] != i) return i + 1; return n+1; } };

------分隔线----------------------------

上一篇 深入,全面正确的理解Android.mk

下一篇 HDU1811Rank of Tetris(并查集+拓扑排序)

------分隔线----------------------------