java实现 给你一个正整数数组 arr(可能存在重复的元素),请你返回可在 一次交换(交换两数字 arr[i] 和 arr[j] 的位置)后得到的、按字典序排列小于 arr 的最大排列。
时间: 2024-05-11 19:17:06 浏览: 12
可以通过以下步骤来实现:
1. 从数组的末尾开始遍历,找到第一个非递增的数 arr[i],记下 i。
2. 如果 i=0,说明整个数组已经是最大排列,直接返回数组的倒序。
3. 从 i+1 到数组末尾再次遍历,找到最后一个比 arr[i] 小的数 arr[j],记下 j。
4. 交换 arr[i] 和 arr[j]。
5. 将 i+1 到数组末尾的数按升序排列,即可得到最终的排列。
以下是 Java 代码实现:
```java
public int[] prevPermOpt1(int[] arr) {
int n = arr.length;
int i = n - 2;
while (i >= 0 && arr[i] <= arr[i + 1]) {
i--;
}
if (i < 0) {
Arrays.sort(arr);
return arr;
}
int j = n - 1;
while (j > i && arr[j] >= arr[i]) {
j--;
}
while (j > 0 && arr[j] == arr[j - 1]) {
j--;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
Arrays.sort(arr, i + 1, n);
return arr;
}
```
其中,Arrays.sort(arr, i + 1, n) 表示对数组 arr 的从下标 i+1 到 n-1 的元素进行升序排列。