给你一个正整数数组 arr(可能存在重复的元素),请你返回可在 一次交换(交换两数字 arr[i] 和 arr[j] 的位置)后得到的、按字典序排列小于 arr 的最大排列。
时间: 2024-05-07 08:18:06 浏览: 14
好的,这是一道比较经典的题目,我来尝试回答一下。
首先需要明确一下,如果一个排列已经是字典序最大的了,那么就不存在交换两个元素后可以得到更小的排列了。
否则,我们可以从右往左找到第一个不满足递减规律的位置 i,也就是说,arr[i] < arr[i+1]。此时,i+1 到 n-1 这一段区间内的元素一定是递减的,因为如果存在某个位置 j 满足 arr[j] > arr[i],那么交换 arr[i] 和 arr[j] 就可以得到更大的排列,与我们要求的最大排列矛盾了。
接下来我们要在 i+1 到 n-1 这一段区间内找到一个比 arr[i] 大的数 arr[j],并且 j 最小。这里可以用二分查找来实现,因为这一段区间内的元素是递减的。找到 j 之后,交换 arr[i] 和 arr[j],再将 i+1 到 n-1 这一段区间内的元素翻转一下,就可以得到字典序小于原排列且字典序最大的排列了。
以下是 C++ 代码实现:
```cpp
vector<int> prevPermOpt1(vector<int>& arr) {
int n = arr.size();
int i = n - 2;
while (i >= 0 && arr[i] <= arr[i+1]) {
i--;
}
if (i < 0) {
return arr;
}
int j = n - 1;
while (j > i && arr[j] >= arr[i]) {
j--;
}
while (j > i && arr[j] == arr[j-1]) {
j--;
}
swap(arr[i], arr[j]);
reverse(arr.begin() + i + 1, arr.end());
return arr;
}
```
希望能够帮到你!