一直寫過數(shù)組全排列的算法，當(dāng)時(shí)接觸的是使用回溯的方法，這樣可以保證生成的全排列一定是按照字典序的，但是今天在做leetcode上的一道題時(shí)，問題是要你找到某個(gè)排列情況的下一個(gè)按照字典序排列的狀態(tài)。
如果直接一點(diǎn)，大可從頭開始做全排列，然后到目標(biāo)狀態(tài)時(shí)，在做一次即可找到要的狀態(tài)，但是如果題目給的狀態(tài)非常靠后，則要花費(fèi)很大的代價(jià)，這樣做就顯得有些笨拙了。
所以做這道題的時(shí)候一直在思考如何按照字典序生成全排列。
假設(shè)此時(shí)給出的狀態(tài)時(shí)5 2 4 3 1，那么下一個(gè)狀態(tài)要如何確定呢？首先從人的視角來看，絕對(duì)會(huì)從序列末尾向前開始查找，例如如果給的狀態(tài)時(shí)1 2 3 4 5，則很容易發(fā)現(xiàn)下一個(gè)狀態(tài)應(yīng)該是1 2 3 5 4，這樣就給出了一個(gè)策略，第一步應(yīng)該先找從末尾開始向前第一對(duì)非逆序數(shù)對(duì)，這當(dāng)然有理由，因?yàn)槿绻悄嫘虻模f明該種情況一定是已經(jīng)進(jìn)行過交換了，則絕對(duì)不會(huì)是下一種情況交換的候選位置，因此會(huì)發(fā)現(xiàn)5 2 4 3 1中第一個(gè)非逆序數(shù)對(duì)是2 4，所以交換的候選對(duì)象應(yīng)該是2（2是較小的那一個(gè)）；緊接著繼續(xù)思考，應(yīng)該和后面的哪一個(gè)進(jìn)行交換。首先顯而易見的是，2后面的子序列一定是逆序的。那么如果要和2交換并且使結(jié)果是字典序的下一個(gè)的話，那么與2交換的一定是2后面的比2大的最小的哪一個(gè)數(shù)，因此第二步就是從序列末尾開始向前查找第一個(gè)比2大的數(shù)，與2進(jìn)行交換（此時(shí)為 5 3 4 2 1），那么下一步也是顯而易見的，3后面的序列應(yīng)該是由5 3開始的字典序最小的一個(gè)序列，因此要將3后面的序列逆置。最后得到答案5 3 1 2 4。
過程并不復(fù)雜，思路和人思考的順序應(yīng)該是一樣的，直接上coding了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
public void reverse(int []nums,int l,int r){ while(l<r){ int tmp=nums[l]; nums[l]=nums[r]; nums[r]=tmp; l++; r--; } } public void nextpermutation(int[] nums) { if(nums.length==0||nums.length==1) return; int i=nums.length-1; for(;i>=1;i--){ if(nums[i]>nums[i-1]) break; } if(i==0){ arrays.sort(nums); return; } int index=i-1; int diff=nums[i-1]; for(i=nums.length-1;i>=0;i--){ if(nums[i]>diff) break; } int tmp=nums[index]; nums[index]=nums[i]; nums[i]=tmp; reverse(nums,index+1,nums.length-1); } |
總結(jié)
以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)服務(wù)器之家的支持。如果你想了解更多相關(guān)內(nèi)容請(qǐng)查看下面相關(guān)鏈接
原文鏈接：https://blog.csdn.net/chaoweilanmaohhh/article/details/79690453
