Previous Permutation With One Swap
找字典序上, 当前数组前一位的permutation. 这个题和next permutation是一套题. 算法就是从后向前找到第一个递减的数, 然后从后网前找到第一个递增的数即可.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public int[] prevPermOpt1(int[] A) { int n = A.length; int j = n - 2; while(j >= 0 && A[j] <= A[j + 1]) j--; if(j == -1) // sorted return A; int max = A[j+1]; int maxIndex = j+1; for(int i = n - 1; i > j; i--) { if(max < A[i] && A[i] < A[j]){ max = A[i]; maxIndex = i; } } int tmp = A[j]; A[j] = A[maxIndex]; A[maxIndex] = tmp; return A; } } |