欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2019年02月18日 15:40:53   作者:chaoweilanmaohhh  
今天小編就為大家分享一篇關(guān)于Java全排列字典序下的下一個排列,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧

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

如果直接一點,大可從頭開始做全排列,然后到目標(biāo)狀態(tài)時,在做一次即可找到要的狀態(tài),但是如果題目給的狀態(tà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)然有理由,因為如果是逆序的,說明該種情況一定是已經(jīng)進行過交換了,則絕對不會是下一種情況交換的候選位置,因此會發(fā)現(xiàn)5 2 4 3 1中第一個非逆序數(shù)對是2 4,所以交換的候選對象應(yīng)該是2(2是較小的那一個);緊接著繼續(xù)思考,應(yīng)該和后面的哪一個進行交換。首先顯而易見的是,2后面的子序列一定是逆序的。那么如果要和2交換并且使結(jié)果是字典序的下一個的話,那么與2交換的一定是2后面的比2大的最小的哪一個數(shù),因此第二步就是從序列末尾開始向前查找第一個比2大的數(shù),與2進行交換(此時為 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)鏈接

相關(guān)文章

  • Java分頁查詢的幾種實現(xiàn)方法舉例

    Java分頁查詢的幾種實現(xiàn)方法舉例

    這篇文章主要給大家介紹了關(guān)于Java分頁查詢的幾種實現(xiàn)方法,分頁是系統(tǒng)中常用到的功能,只要涉及到查詢必定伴隨而來的就是分頁,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下
    2023-06-06
  • Spring中的ThreadPoolTaskExecutor線程池使用詳解

    Spring中的ThreadPoolTaskExecutor線程池使用詳解

    這篇文章主要介紹了Spring中的ThreadPoolTaskExecutor線程池使用詳解,ThreadPoolTaskExecutor 是 Spring框架提供的一個線程池實現(xiàn),用于管理和執(zhí)行多線程任務(wù),它是TaskExecutor接口的實現(xiàn),提供了在 Spring 應(yīng)用程序中創(chuàng)建和配置線程池的便捷方式,需要的朋友可以參考下
    2024-01-01
  • Java操作Redis2種方法代碼詳解

    Java操作Redis2種方法代碼詳解

    這篇文章主要介紹了Java操作Redis2種方法代碼詳解,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2020-04-04
  • 解決spring-boot2.0.6中webflux無法獲得請求IP的問題

    解決spring-boot2.0.6中webflux無法獲得請求IP的問題

    這幾天在用 spring-boot 2 的 webflux 重構(gòu)一個工程,寫到了一個需要獲得客戶端請求 IP 的地方,在寫的過程中遇到很多問題,下面小編通過一段代碼給大家介紹解決spring-boot2.0.6中webflux無法獲得請求IP的問題,感興趣的朋友跟隨小編一起看看吧
    2018-10-10
  • 淺談java中String的兩種賦值方式的區(qū)別

    淺談java中String的兩種賦值方式的區(qū)別

    這篇文章主要介紹了淺談java中String的兩種賦值方式的區(qū)別。簡單介紹了兩種賦值方式,然后進行了實例分析,具有一定參考價值,需要的朋友可以了解下。
    2017-11-11
  • Java中MyBatis傳入?yún)?shù)parameterType問題

    Java中MyBatis傳入?yún)?shù)parameterType問題

    這篇文章主要介紹了Java中MyBatis傳入?yún)?shù)parameterType問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-12-12
  • Java模擬QQ實現(xiàn)聊天互動程序

    Java模擬QQ實現(xiàn)聊天互動程序

    這篇文章主要介紹了如何利用Java語言模擬QQ實現(xiàn)一個簡易的聊天互動程序,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2022-06-06
  • 使用Java注解和反射實現(xiàn)JSON字段自動重命名

    使用Java注解和反射實現(xiàn)JSON字段自動重命名

    這篇文章主要介紹了如何使用Java注解和反射實現(xiàn)JSON字段自動重命名,文中通過代碼示例和圖文介紹的非常詳細,對大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下
    2024-08-08
  • SpringBoot實現(xiàn)的Mongodb管理工具使用解析

    SpringBoot實現(xiàn)的Mongodb管理工具使用解析

    這篇文章主要介紹了SpringBoot實現(xiàn)的Mongodb管理工具使用解析,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2019-09-09
  • Spring security密碼加密實現(xiàn)代碼實例

    Spring security密碼加密實現(xiàn)代碼實例

    這篇文章主要介紹了Spring security密碼加密實現(xiàn)代碼實例,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2020-04-04

最新評論