Python 中的下一个排列

假设我们要实现下一个排列方法，该方法将数字重新排列成数字下一个更大的字典排列顺序。如果这种安排不可行，该方法会将排列重新排列为最低可能的顺序（即实际按升序排列）。替换必须就地进行，并且不使用任何额外的内存。例如，如果输入位于左侧栏，则其相应输出位于右侧栏。

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

让我们看这些步骤 −

  • found := false, i := 数组长度 - 2
  • while i >= 0
    • 如果 A[i] < A[i + 1]，则 found := True，并终止循环
    • 将 i 增加 1
  • 如果 found := false，则对数组 A 进行排序，
  • 否则
    • m := 从索引 i + 1 中找到最大元素索引，从 A 中找到，从当前元素 A[i] 中找到
    • 交换元素 A[i] 和 A[m]
    • 将 A 中的 i+1 到末尾的所有元素倒置

让我们看一下以下实现以获得更好的理解 −

示例

 实时演示

class Solution(object):
   def nextPermutation(self, nums):
      found = False
      i = len(nums)-2
      while i >=0:
         if nums[i] < nums[i+1]:
            found =True
            break
         i-=1
      if not found:
         nums.sort()
      else:
         m = self.findMaxIndex(i+1,nums,nums[i])
         nums[i],nums[m] = nums[m],nums[i]
         nums[i+1:] = nums[i+1:][::-1]
      return nums
   def findMaxIndex(self,index,a,curr):
      ans = -1
      index = 0
      for i in range(index,len(a)):
         if a[i]>curr:
            if ans == -1:
               ans = curr
               index = i
            else:
               ans = min(ans,a[i])
               index = i
      return index
ob1 = Solution()
print(ob1.nextPermutation([1,2,5,4,3]))

输入

[1,2,5,4,3]

输出

[1, 3, 2, 4, 5]

更新于： 04-May-2020

4K+ 浏览

开始你的职业生涯

通过完成课程获得认证

开始
广告