快捷導(dǎo)航

Java全排列算法字典序下的下一個排列講解

更新時間：2019年02月18日 15:40:53 作者：chaoweilanmaohhh

今天小編就為大家分享一篇關(guān)于Java全排列字典序下的下一個排列，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧

一直寫過數(shù)組全排列的算法，當(dāng)時接觸的是使用回溯的方法，這樣可以保證生成的全排列一定是按照字典序的，但是今天在做leetcode上的一道題時，問題是要你找到某個排列情況的下一個按照字典序排列的狀態(tài)。

如果直接一點(diǎn)，大可從頭開始做全排列，然后到目標(biāo)狀態(tài)時，在做一次即可找到要的狀態(tài)，但是如果題目給的狀態(tài)非?？亢螅瑒t要花費(fèi)很大的代價，這樣做就顯得有些笨拙了。

所以做這道題的時候一直在思考如何按照字典序生成全排列。

假設(shè)此時給出的狀態(tài)時5 2 4 3 1，那么下一個狀態(tài)要如何確定呢？首先從人的視角來看，絕對會從序列末尾向前開始查找，例如如果給的狀態(tài)時1 2 3 4 5，則很容易發(fā)現(xiàn)下一個狀態(tài)應(yīng)該是1 2 3 5 4，這樣就給出了一個策略，第一步應(yīng)該先找從末尾開始向前第一對非逆序數(shù)對，這當(dāng)然有理由，因?yàn)槿绻悄嫘虻?，說明該種情況一定是已經(jīng)進(jìn)行過交換了，則絕對不會是下一種情況交換的候選位置，因此會發(fā)現(xiàn)5 2 4 3 1中第一個非逆序數(shù)對是2 4，所以交換的候選對象應(yīng)該是2（2是較小的那一個）；緊接著繼續(xù)思考，應(yīng)該和后面的哪一個進(jìn)行交換。首先顯而易見的是，2后面的子序列一定是逆序的。那么如果要和2交換并且使結(jié)果是字典序的下一個的話，那么與2交換的一定是2后面的比2大的最小的哪一個數(shù)，因此第二步就是從序列末尾開始向前查找第一個比2大的數(shù)，與2進(jìn)行交換（此時為 5 3 4 2 1），那么下一步也是顯而易見的，3后面的序列應(yīng)該是由5 3開始的字典序最小的一個序列，因此要將3后面的序列逆置。最后得到答案5 3 1 2 4。

過程并不復(fù)雜，思路和人思考的順序應(yīng)該是一樣的，直接上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);
  }

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，謝謝大家對腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請查看下面相關(guān)鏈接

您可能感興趣的文章: