您当前位置：首页 > php开源 > php教程 > LeetCode First Missing Positive

LeetCode First Missing Positive

来源：程序员人生发布时间：2015-03-09 09:04:25 阅读次数：3112次

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(并查集+拓扑排序)

分享到:

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

为码而活

积分：4237

15粉丝

7关注

栏目热点