使用Python进行一次交换的先前排列

假设我们有一个由正整数组成的数组A（不一定是唯一的），我们必须找到一个小于A的按字典顺序排列的最大排列，可以通过一次交换实现（一次交换交换两个数字A [i]和A [j]）。如果不可能，则返回相同的数组。因此，如果数组类似于[3,2,1]，则通过交换2和1，输出将为[3,1,2]

为了解决这个问题，我们将遵循以下步骤-

• n：= A的大小

• 在范围n – 2到-1之间

• 如果left = -1，则返回A，否则返回A [left]> A [left + 1]，然后中断

• 元素：= 0，索引：= 0

• 对于在左+ 1至n范围内的右

• 元素= A [右]

• 索引：=对

• 如果A [right] <A [left]和A [right]>元素，则

• 交换A [左]和A [索引]

• 返回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]