一取董、題目
實(shí)現(xiàn)獲取下一個(gè)排列的函數(shù)，算法需要將給定數(shù)字序列重新排列成字典序中下一個(gè)更大的排列。
如果不存在下一個(gè)更大的排列淮蜈，則將數(shù)字重新排列成最小的排列（即升序排列）。
必須原地修改已卷，只允許使用額外常數(shù)空間梧田。
以下是一些例子，輸入位于左側(cè)列侧蘸，其相應(yīng)輸出位于右側(cè)列裁眯。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
二、解題
這道題讓我們求下一個(gè)排列順序讳癌，有題目中給的例子可以看出來穿稳，如果給定數(shù)組是降序，則說明是全排列的最后一種情況晌坤，則下一個(gè)排列就是最初始情況逢艘，可以參見之前的博客 Permutations 全排列旦袋。我們再來看下面一個(gè)例子，有如下的一個(gè)數(shù)組
1 2 7 4 3 1
下一個(gè)排列為：
1 3 1 2 4 7
那么是如何得到的呢它改，我們通過觀察原數(shù)組可以發(fā)現(xiàn)疤孕，如果從末尾往前看，數(shù)字逐漸變大央拖，到了2時(shí)才減小的祭阀，然后我們再從后往前找第一個(gè)比2大的數(shù)字，是3爬泥，那么我們交換2和3柬讨，再把此時(shí)3后面的所有數(shù)字轉(zhuǎn)置一下即可，步驟如下：
1 2 7 4 3 1
1 2 7 4 3 1
1 3 7 4 2 1
1 3 1 2 4 7
三袍啡、代碼實(shí)現(xiàn)
class Solution {
func nextPermutation(_ nums: inout [Int]) {
var j = nums.count
for i in stride(from: nums.count-2, through: 0, by: -1) {
if nums[i+1] > nums[i] {
for k in stride(from: nums.count-1, to: i, by: -1) {
j = k
if nums[k] > nums[i] {
break
}
}
nums.swapAt(i, j)
nums[i+1..<nums.count].sort()
return
}
}
nums.sort()
}
}
Demo地址：github
