First Missing Positive:テストサンプルに困惑している問題
1062 ワード
Given an unsorted integer array, find the first missing positive integer.
For example, Given
Your algorithm should run in O(n) time and uses constant space. 困惑:どうして[6,7]答えが5のこのようなテストのサンプルではありませんか??理解できません...
Acceptの答えはi位置にi+1要素を保存することであり,最後にアクセスしたときに対応できない点が答えである.
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. 困惑:どうして[6,7]答えが5のこのようなテストのサンプルではありませんか??理解できません...
Acceptの答えはi位置にi+1要素を保存することであり,最後にアクセスしたときに対応できない点が答えである.
class Solution {
public int firstMissingPositive(int[] A) {
if (A == null || A.length < 1) return 1;
// A.length A[i] A[i]-1
for (int i = 0; i < A.length; i++) {
while (A[i] > 0 && A[i] <= A.length && A[A[i] - 1] != A[i]) {
int tmp = A[A[i] - 1];
A[A[i] - 1] = A[i];
A[i] = tmp;
}
}
for (int i = 0; i < A.length; i++) {
if (A[i] != i + 1) {
return i + 1;
}
}
return A.length + 1;
}
}