[LeetCode] 1053. Previous Permutation With One Swap 交换一次的先前全排列

Given an array of positive integers arr
 (not necessarily distinct), return the lexicographically largest permutation that is smaller than arr
, that can be made with exactly one swap (A swap exchanges the positions of two numbers arr[i]
 and arr[j]
). If it cannot be done, then return the same array.

Example 1:

Input: arr = [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.
复制

Example 2:

Input: arr = [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.
复制

Example 3:

Input: arr = [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.
复制

Example 4:

Input: arr = [3,1,1,3]
Output: [1,3,1,3]
Explanation: Swapping 1 and 3.
复制

Constraints:

•1 <= arr.length <= 104
•1 <= arr[i] <= 104

这道题给了一个正整数的数组，说是让任意交换两个数字，使得变成字母顺序最大的一种全排列，但是需要小于原先的排列，若无法得到这样的全排列（说明当前已经是最小的全排列），则返回原数组。通过分析题目中给的例子不难理解题意，根据例子2来看，若给定的数组就是升序排列的，则无法得到更小的全排列，说明只有遇到降序的位置的时候，才有可能进行交换。但是假如有多个可以下降的地方呢，比如例子1，3到2下降，2到1下降，这里是需要交换2和1的，所以最好是从后往前检验，遇到前一个数字比当前数字大的情况时，前一个数字必定是交换方之一，而当前数字并不是。比如例子3，数字4的前面是9，正确结果是9和7交换，所以还要从4往后遍历一下，找到一个仅次于9的数字交换才行，而且数字相同的话，取坐标较小的那个，比如例子4就是这种情况。其实这道题的四个例子给的真不错，基本各种情况都 cover 到了，赞一个～ 分析到这里，代码就不难写了，首先从后往前遍历，假如当前数字大于等于前一个数字，直接跳过，否则说明需要交换的。从当前位置再向后遍历一遍，找到第一个仅次于拐点的数字交换即可，注意下面的代码虽然嵌套了两个 for 循环，其实是线性的时间复杂度，参见代码如下：

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& arr) {
        int n = arr.size(), mx = 0, idx = -1;
        for (int i = n - 1; i > 0; --i) {
            if (arr[i] >= arr[i - 1]) continue;
            for (int j = i; j < n; ++j) {
                if (arr[j] < arr[i - 1] && mx < arr[j]) {
                    mx = arr[j];
                    idx = j;
                }
            }
            swap(arr[i - 1], arr[idx]);
            break;
        }
        return arr;
    }
};
复制

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1053

参考资料：

https://leetcode.com/problems/previous-permutation-with-one-swap/

https://leetcode.com/problems/previous-permutation-with-one-swap/discuss/838836/Java-O(n)

https://leetcode.com/problems/previous-permutation-with-one-swap/discuss/299244/Similar-to-find-previous-permutation-written-in-Java

LeetCode All in One 题目讲解汇总(持续更新中...)^[1]

References

[1]
 LeetCode All in One 题目讲解汇总(持续更新中...): https://www.cnblogs.com/grandyang/p/4606334.html