leetcode31 Next Permutation

hedzr 發(fā)布于2019-08-16 10:34 / 3302人閱讀

摘要：如果當(dāng)前數(shù)字代表的整數(shù)值已經(jīng)是所有排列組合中的最大值，則返回當(dāng)前數(shù)字組成的最小值。可是這意味著大量無用的數(shù)字的生成和比較。一個數(shù)字中的各個位上的數(shù)如何調(diào)整順序才能獲得一個最小的更大值。其次，要保證移動之后，高位以后的值為最小值。

題目要求

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

翻譯過來就是說，輸入一個整數(shù)數(shù)組，該整數(shù)數(shù)組按照下標(biāo)順序代表一個數(shù)字，例如[1,2,3]代表整數(shù)123，要求改變數(shù)組中元素的順序，找到比當(dāng)前數(shù)字大的生成數(shù)中的最小值。如果當(dāng)前數(shù)字代表的整數(shù)值已經(jīng)是所有排列組合中的最大值，則返回當(dāng)前數(shù)字組成的最小值。

思路分析

如何才能找到一個值，不是過大也不是過小呢？其實，找到這幾個數(shù)字所有排列組合的可能性，然后再和當(dāng)前數(shù)字一一進(jìn)行比較其實也是一個思路。可是這意味著大量無用的數(shù)字的生成和比較。想要知道如何生成所有排列組合結(jié)果，可以參考我的這篇博客
換句話說，我們要盡量用最少的比較的到最小的結(jié)果。一個數(shù)字中的各個位上的數(shù)如何調(diào)整順序才能獲得一個最小的更大值。首先，可以將低位移到高位，只要低位的數(shù)字比高位上的數(shù)字大。但是，為了確保的到盡可能小的最大值，一定要將移動的位確保越小越好。其次，要保證移動之后，高位以后的值為最小值。
綜上所述，思路如下：

由最低位（下表為nums.length-2)開始，由低往高遍歷，找到可以進(jìn)行替換的最小位。

可以替換的條件是，比當(dāng)前位低的位上存在一個數(shù)，該數(shù)比當(dāng)前位上的值大，且不存在另一個比該值小且比當(dāng)前位上值大的數(shù)

替換數(shù)值后，該進(jìn)行替換的位后序的位上的值應(yīng)當(dāng)保證為最小值。

例如[1，3，2]，將百位上的值和個位上的值替換以后，還要保證百位以后的值為最小值，所以最后的結(jié)果為[2,1,3]

實現(xiàn)代碼如下

    public void nextPermutation(int[] nums) {
        for(int i = nums.length - 2 ; i>=0 ; i--){
            //尋找可以替換的最低位
            for(int j = i+1 ; j

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~