leetcode31 Next Permutation

hedzr 發布于2019-08-16 10:34 / 3296人閱讀

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

題目要求

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

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

思路分析

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

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

可以替換的條件是，比當前位低的位上存在一個數，該數比當前位上的值大，且不存在另一個比該值小且比當前位上值大的數

替換數值后，該進行替換的位后序的位上的值應當保證為最小值。

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

實現代碼如下

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

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Permutation Leetcod LeetCode -next

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/70049.html

leetcode 31 Next Permutation

摘要：我們所找到的這個元素就是排序需要改變的第一個元素。然后我們選取一個剛好大于此元素的數，與當前元素進行替換。并對后面的所有元素重新按照升序排列就可以得到最終的答案。題目詳情 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of...

binaryTree 2019-08-19 10:41 評論0 收藏0
31. Next Permutation

摘要：邊界條件，這時候之后只有一個值數組一直遞減，這時候變成，沒有，只需要從到的所有數。 31. Next Permutation 題目鏈接：https://leetcode.com/problems... 這道題就是找規律，可以看出來下一個permutation的規律是：從右往左掃，找到第一個滿足：nums[i-1] < nums[i]條件的，再找到從右到左第一個比nums[i-1]大的數...

未東興 2019-08-14 17:26 評論0 收藏0
[Leetcode] Next Permutation 下一個排列

摘要：因為增加高位會帶來更大的增益。所以對于一個長為的序列，我們增加第位的前提是，前位已經達到了最大排列方法。因為是找下一個數，所以我們要找一個比小卻盡可能大的數，所以找到。把換到的位置后，后三位仍然是個降序的排列。 Next Permutation Implement next permutation, which rearranges numbers into the lexicogr...

young.li 2019-08-14 12:34 評論0 收藏0
[Leetcode]PermutationsI II Next Permutation Permut

摘要：解題思路這道題是要將排列按字典序排列，然后求出下一個排列，一種辦法是我們先求出所有的排序情況，但是題目規定不能占有額外空間。每次求出一個數字后，要及時的把它從中刪除掉。采用來構造結果序列。 PermutationsGiven a collection of distinct numbers, return all possible permutations. For example, ...

ChristmasBoy 2019-08-16 10:26 評論0 收藏0
31. Next Permutation

摘要：比如我們很容易知道下一個數字是。從尾到頭找，第一段的部分出現。后面的部分就可以有更大的組合。這里是在遞減序列中找到下一個比大的數字，作為序列的頭。尾部的遞減序列變成遞增序列。 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation o...

denson 2019-08-16 10:34 評論0 收藏0