原文链接: https://leetcode-cn.com/problems/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

中文题目

给你一个正整数的数组 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 <= 104
• 1 <= arr[i] <= 104

通过代码

高赞题解

审题是最关键的，首先明确以下几点：

1. 正整数的数组A的元素可能存在相同元素
2. 要进行一次交换
3. 找出按字典序排列小于 A 的最大可能排列

根据示例总结规律：

1. 升序排列的数组无需交换

2. 确定需要交换元素的位置：

   对数组元素组成的数据而言，最接近这个数的排列逆序查找，第一次升序的位置，如下图：

在第一次升序的位置，左侧元素A[i-1]大于当前元素A[i]，即A[i-1]>A[i]，例如：

• [3,2,1]中箭头左侧2>1
• [1,9,4,6,7]中箭头左侧9>4
• [3,1,1,3]中箭头左侧3>1

所以一定能构造出比当前字典序列小的数据，左侧的元素A[i-1]就是要要交换的元素，如下图框中元素：

3. 从箭头所在的位置开始，查找当前位置和右侧所有元素，且这个元素A[j]要满足以下条件：

   • 这个元素值最大且小于要交换的元素的值A[i-1]
   • 这个元素最靠近要交换的元素A[i-1]（主要是考虑右侧元素相等的情况，如3113，交换左侧1以保证元素组成的数据最大）

   可以明确的是，箭头右侧的数据是从右向左是降序排列的，所以可以直接逆序查找。如果第一个小于A[i-1]的元素如果满足与他的左侧数据不相等，那么这个元素就是要交换的元素A[j]。
   

4. 找出要交换的两个元素A[i-1]和A[j]后，进行交换，则交换后的学列字典序一定是小于当前字典序，且组成的数据是最大的一条。

python3 代码也很简单，参考如下：

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        lenth = len(A)
        for i in range(lenth-1, 0, -1):
            # 第一次升序的位置，左侧元素A[i-1]大于当前元素A[i]
            if A[i-1] > A[i]:
                # 逆序从结尾向第i-1个索引查找A[j]           
                for j in range(lenth-1, i-1, -1):
                    # 元素要满足小于A[i-1]且与左侧元素不相等就是要找的最大元素
                    if A[j] < A[i-1] and A[j] != A[j-1]:
                        A[i-1],A[j] = A[j],A[i-1]
                        return A
        return A

统计信息

通过次数	提交次数	AC比率
6097	13277	45.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言