資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會科學
時尚研究
法律研究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+ 瀏覽
廣告