Java全排列算法字典序下的下一個排列講解
一直寫過數(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)文章
Spring中的ThreadPoolTaskExecutor線程池使用詳解
這篇文章主要介紹了Spring中的ThreadPoolTaskExecutor線程池使用詳解,ThreadPoolTaskExecutor 是 Spring框架提供的一個線程池實現(xiàn),用于管理和執(zhí)行多線程任務(wù),它是TaskExecutor接口的實現(xiàn),提供了在 Spring 應(yīng)用程序中創(chuàng)建和配置線程池的便捷方式,需要的朋友可以參考下2024-01-01解決spring-boot2.0.6中webflux無法獲得請求IP的問題
這幾天在用 spring-boot 2 的 webflux 重構(gòu)一個工程,寫到了一個需要獲得客戶端請求 IP 的地方,在寫的過程中遇到很多問題,下面小編通過一段代碼給大家介紹解決spring-boot2.0.6中webflux無法獲得請求IP的問題,感興趣的朋友跟隨小編一起看看吧2018-10-10Java中MyBatis傳入?yún)?shù)parameterType問題
這篇文章主要介紹了Java中MyBatis傳入?yún)?shù)parameterType問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-12-12使用Java注解和反射實現(xiàn)JSON字段自動重命名
這篇文章主要介紹了如何使用Java注解和反射實現(xiàn)JSON字段自動重命名,文中通過代碼示例和圖文介紹的非常詳細,對大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下2024-08-08SpringBoot實現(xiàn)的Mongodb管理工具使用解析
這篇文章主要介紹了SpringBoot實現(xiàn)的Mongodb管理工具使用解析,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-09-09Spring security密碼加密實現(xiàn)代碼實例
這篇文章主要介紹了Spring security密碼加密實現(xiàn)代碼實例,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-04-04