Python 中一次交换的上一个排列
pythonserver side programmingprogramming更新于 2023/10/5 8:54:00
假设我们有一个正整数数组 A(不一定是唯一的)，我们必须找到按字典顺序排列的、小于 A 的最大排列，该排列可以通过一次交换完成(交换两个数字 A[i] 和 A[j] 的位置)。如果不可能，则返回相同的数组。因此，如果数组为 [3,2,1]，则输出将为 [3,1,2]，通过交换 2 和 1
要解决这个问题，我们将遵循以下步骤 −
- n := A 的大小
- 对于范围从 n – 2 到 -1 的左侧
- 如果 left = -1，则返回 A，否则当 A[left] > A[left + 1]，然后中断
- 元素 := 0，索引 := 0
- 对于 left + 1 到 n 范围内的 right
- 如果 A[right] < A[left] 和 A[right] > 元素，则
- 元素 = A[right]
- 索引 := right
- 如果 A[right] < A[left] 和 A[right] > 元素，则
- 交换 A[left] 和 A[index]
- 返回 A
让我们看看下面的实现以便更好地理解 −
示例
class Solution(object): def prevPermOpt1(self, A): n = len(A) for left in range(n-2,-2,-1): if left == -1: return A elif A[left]>A[left+1]: break element = 0 index = 0 for right in range(left+1,n): if A[right]<A[left] and A[right]>element: element = A[right] index = right temp = A[left] A[left] = A[index] A[index] = temp return A ob = Solution() print(ob.prevPermOpt1([4,2,3,1,3]))
输入
[4,2,3,1,3]
输出
[4, 2, 1, 3, 3]
