溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
一直寫過數組全排列的算法，當時接觸的是使用回溯的方法，這樣可以保證生成的全排列一定是按照字典序的，但是今天在做leetcode上的一道題時，問題是要你找到某個排列情況的下一個按照字典序排列的狀態。
如果直接一點，大可從頭開始做全排列，然后到目標狀態時，在做一次即可找到要的狀態，但是如果題目給的狀態非常靠后，則要花費很大的代價，這樣做就顯得有些笨拙了。
所以做這道題的時候一直在思考如何按照字典序生成全排列。
假設此時給出的狀態時5 2 4 3 1，那么下一個狀態要如何確定呢？首先從人的視角來看，絕對會從序列末尾向前開始查找，例如如果給的狀態時1 2 3 4 5，則很容易發現下一個狀態應該是1 2 3 5 4，這樣就給出了一個策略，第一步應該先找從末尾開始向前第一對非逆序數對，這當然有理由，因為如果是逆序的，說明該種情況一定是已經進行過交換了，則絕對不會是下一種情況交換的候選位置，因此會發現5 2 4 3 1中第一個非逆序數對是2 4，所以交換的候選對象應該是2（2是較小的那一個）；緊接著繼續思考，應該和后面的哪一個進行交換。首先顯而易見的是，2后面的子序列一定是逆序的。那么如果要和2交換并且使結果是字典序的下一個的話，那么與2交換的一定是2后面的比2大的最小的哪一個數，因此第二步就是從序列末尾開始向前查找第一個比2大的數，與2進行交換（此時為 5 3 4 2 1），那么下一步也是顯而易見的，3后面的序列應該是由5 3開始的字典序最小的一個序列，因此要將3后面的序列逆置。最后得到答案5 3 1 2 4。
過程并不復雜，思路和人思考的順序應該是一樣的，直接上coding了。
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);
}
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對億速云的支持。如果你想了解更多相關內容請查看下面相關鏈接
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
