跳转至

LeetCode: 1053. 交换一次的先前排列

1、题目描述

给你一个正整数的数组 A(其中的元素不一定完全不同),请你返回可在 一次交换(交换两数字 A[i]A[j] 的位置)后得到的、按字典序排列小于 A 的最大可能排列。

如果无法这么操作,就请返回原数组。

示例 1:

输入:[3,2,1]
输出:[3,1,2]
解释:
交换 2 和 1

示例 2:

输入:[1,1,5]
输出:[1,1,5]
解释: 
这已经是最小排列

示例 3:

输入:[1,9,4,6,7]
输出:[1,7,4,6,9]
解释:
交换 9 和 7

示例 4:

输入:[3,1,1,3]
输出:[1,3,1,3]
解释:
交换 1 和 3

提示:

  • 1 <= A.length <= 10000
  • 1 <= A[i] <= 10000

2、解题思路

  • 首先从右向左寻找,找到第一个逆序
  • 然后从逆序位置向右寻找,找出仅次于逆序数字的位置进行交换即可
[3,2,1]
第一个逆序位置为1,数字是2,从逆序位置向向右寻找,仅次于数字2的位置
交换的到结果:
[3,1,2]

=======================================================
[1,9,4,6,7]
逆序对是[9,4],位置为1,向右寻找仅次于当前数字的那个位置,也就是7对应的位置
得到结果
[1,7,4,6,9]
class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        length = len(A)
        left = length

        for i in range(length - 1, 0, -1):
            if A[i] < A[i - 1]:
                left = i - 1
                break
        if left < length:
            right = left + 1
            for i in range(left + 2, length):
                if A[left] > A[i] > A[i - 1]:
                    right = i
            A[left], A[right] = A[right], A[left]

        return A