用一次交換在 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 次瀏覽

開始你的 職業生涯

透過完成課程獲得認證

開始
廣告