题目
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 + 1。
代码
public class FirstMissingPositive { public int firstMissingPositive(int[] A) { if (A == null || A.length == 0) { return 1; } int N = A.length; for (int i = 0; i < N; ++i) { if (A[i] <= 0) { A[i] = N + 1; } } for (int i = 0; i < N; ++i) { if (Math.abs(A[i]) <= N) { int index = Math.abs(A[i]) - 1; A[index] = -Math.abs(A[index]); } } for (int i = 0; i < N; ++i) { if (A[i] > 0) { return i + 1; } } return N + 1; } }
LeetCode | First Missing Positive,布布扣,bubuko.com
LeetCode | First Missing Positive
原文:http://blog.csdn.net/perfect8886/article/details/22572577