05 August 2008
给一个正整数数组 arr（不一定是不同的），返回小于 arr 的字典序上最大的排列，这可以通过恰好一次交换来实现（交换交换两个数字 arr[i] 和 arr[j] 的位置）。如果无法完成，则返回相同的数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int[] prevPermOpt1(int[] arr) {
for (int i = arr.length - 1; i >= 0; i--) {
int diff = Integer.MAX_VALUE;
int index = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] - arr[j] > 0) {
if (diff > arr[i] - arr[j]) {
diff = arr[i] - arr[j];
index = j;
}
}
}
if (diff != Integer.MAX_VALUE) {
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
break;
}
}
return arr;
}
}