First Missing Positive:テストサンプルに困惑している問題

1062 ワード

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. 困惑:どうして[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;  
    }  
}