Python 中的下一个排列

pythonserver side programmingprogramming更新于 2025/11/18 22:04:17

假设我们想要实现下一个排列方法，该方法将数字重新排列为按字典顺序排列的下一个更大的数字排列。如果无法进行这样的排列，则此方法将按最低可能的顺序重新排列(实际上是按升序排序)。替换必须是就地的，并且不占用任何额外的内存。例如，如果输入在左列，其对应的输出在右列。

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

让我们看看步骤 −

found := false, i := 数组的长度 – 2
当 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]))