用一次交换在 Python 中实现前一个排列

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

为了解决这个问题，我们将按照以下步骤进行 -

  • n := A 的大小
  • 对于 left 从范围 n - 2 到 -1
    • 如果 left = -1，则返回 A，否则当 A[left] > A[left + 1] 时，则中断
  • element := 0，index := 0
  • 对于 right 范围 left + 1 到 n
    • 如果 A[right] < A[left] 且 A[right] > element，则
      • element = A[right]
      • index := 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]

更新于：2020 年 4 月 30 日

329 次浏览

开始你的 职业生涯

通过完成课程获得认证

开始
广告