class Solution {
public:
vector<int> prevPermOpt1(vector<int>& arr) {
}
};
1053. 交换一次的先前排列
给你一个正整数的数组 A（其中的元素不一定完全不同），请你返回可在 一次交换（交换两数字 A[i] 和 A[j] 的位置）后得到的、按字典序排列小于 A 的最大可能排列。
如果无法这么操作，就请返回原数组。
示例 1：
输入：arr = [3,2,1] 输出：[3,1,2] 解释：交换 2 和 1
示例 2：
输入：arr = [1,1,5] 输出：[1,1,5] 解释：已经是最小排列
示例 3：
输入：arr = [1,9,4,6,7] 输出：[1,7,4,6,9] 解释：交换 9 和 7
示例 4：
输入：arr = [3,1,1,3] 输出：[1,3,1,3] 解释：交换 1 和 3
提示：
1 <= arr.length <= 1041 <= arr[i] <= 104原站题解
javascript 解法, 执行用时: 112 ms, 内存消耗: 46.3 MB, 提交时间: 2023-04-03 09:14:41
/**
* @param {number[]} arr
* @return {number[]}
*/
var prevPermOpt1 = function(arr) {
const n = arr.length;
for (let i = n - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1]) {
let j = n - 1;
while (arr[j] >= arr[i] || arr[j] == arr[j - 1]) {
j--;
}
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
break;
}
}
return arr;
};
golang 解法, 执行用时: 28 ms, 内存消耗: 6.6 MB, 提交时间: 2023-04-03 09:14:14
func prevPermOpt1(arr []int) []int {
for i := len(arr) - 2; i >= 0; i-- {
if arr[i] > arr[i + 1] {
j := len(arr) - 1
for arr[j] >= arr[i] || arr[j] == arr[j - 1] {
j--
}
arr[i], arr[j] = arr[j], arr[i]
break
}
}
return arr
}
python3 解法, 执行用时: 48 ms, 内存消耗: 16 MB, 提交时间: 2023-04-03 09:13:49
class Solution:
def prevPermOpt1(self, arr: List[int]) -> List[int]:
n = len(arr)
for i in range(n - 2, -1, -1):
if arr[i] > arr[i + 1]:
j = n - 1
while arr[j] >= arr[i] or arr[j] == arr[j - 1]:
j -= 1
arr[i], arr[j] = arr[j], arr[i]
break
return arr
java 解法, 执行用时: 0 ms, 内存消耗: 42.8 MB, 提交时间: 2023-04-03 09:13:33
class Solution {
public int[] prevPermOpt1(int[] arr) {
int n = arr.length;
for (int i = n - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1]) {
int j = n - 1;
while (arr[j] >= arr[i] || arr[j] == arr[j - 1]) {
j--;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
break;
}
}
return arr;
}
}
cpp 解法, 执行用时: 20 ms, 内存消耗: 24 MB, 提交时间: 2023-04-03 09:13:19
class Solution {
public:
vector<int> prevPermOpt1(vector<int>& arr) {
int n = arr.size();
for (int i = n - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1]) {
int j = n - 1;
while (arr[j] >= arr[i] || arr[j] == arr[j - 1]) {
j--;
}
swap(arr[i], arr[j]);
break;
}
}
return arr;
}
};