成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode 31 Next Permutation

binaryTree / 823人閱讀

摘要：我們所找到的這個(gè)元素就是排序需要改變的第一個(gè)元素。然后我們選取一個(gè)剛好大于此元素的數(shù)，與當(dāng)前元素進(jìn)行替換。并對(duì)后面的所有元素重新按照升序排列就可以得到最終的答案。

題目詳情 
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. 
題目的意思是找到當(dāng)前元素排列的‘下一個(gè)排列’。那么什么叫‘下一個(gè)排列呢’？這里舉個(gè)例子，比如說(shuō)元素1，2，3。它們的全排列是‘1，2，3’，‘1，3，2’，‘2，1，3’，‘2，3，1’，‘3，1，2’，‘3，2，1’因此比如求‘123’的下一個(gè)排列，就應(yīng)該返回‘1，3，2’.
如果當(dāng)前的序列不存在‘下一個(gè)排列’，那么就返回完全升序的第一個(gè)排列。


例子： 左側(cè)一列是輸入，右側(cè)是正確的輸出：
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
想法

當(dāng)我們要求一個(gè)排列的‘下一個(gè)排列’，我們需要意識(shí)到問(wèn)題的關(guān)鍵在于從數(shù)組末端遍歷到的，第一個(gè)不滿足nums[i] <= nums[i+1]條件的元素。

我們所找到的這個(gè)元素就是排序需要改變的第一個(gè)元素。

然后我們選取一個(gè)剛好大于此元素的數(shù)，與當(dāng)前元素進(jìn)行替換。并對(duì)后面的所有元素重新按照升序排列就可以得到最終的答案。

我描述的不是很清晰，這里引用一張leetcode上的圖講解

解法 
    public void nextPermutation(int[] nums) {
        int length = nums.length;
        int i= length-2;
        while(i>=0 && nums[i+1] <= nums[i])i--;
        if(i >= 0){
            int j = length -1;
            while(j >= 0 && nums[j] <= nums[i])j--;
            swap(nums,i,j);
        }
        reverse(nums,i+1);
    }
    
    public void reverse(int[] nums,int start){
        int end = nums.length-1;
        while(start < end){
            swap(nums,start,end);
            start ++;
            end --;
        }
    }
    
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/76314.html

相關(guān)文章

  • leetcode31 Next Permutation

    摘要：如果當(dāng)前數(shù)字代表的整數(shù)值已經(jīng)是所有排列組合中的最大值，則返回當(dāng)前數(shù)字組成的最小值?？墒沁@意味著大量無(wú)用的數(shù)字的生成和比較。一個(gè)數(shù)字中的各個(gè)位上的數(shù)如何調(diào)整順序才能獲得一個(gè)最小的更大值。其次，要保證移動(dòng)之后，高位以后的值為最小值。 題目要求 Implement next permutation, which rearranges numbers into the lexicographi...

    hedzr 評(píng)論0 收藏0

  • 31. Next Permutation

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

    未東興 評(píng)論0 收藏0

  • [Leetcode] Next Permutation 下一個(gè)排列

    摘要：因?yàn)樵黾痈呶粫?huì)帶來(lái)更大的增益。所以對(duì)于一個(gè)長(zhǎng)為的序列，我們?cè)黾拥谖坏那疤崾?，前位已?jīng)達(dá)到了最大排列方法。因?yàn)槭钦蚁乱粋€(gè)數(shù)，所以我們要找一個(gè)比小卻盡可能大的數(shù)，所以找到。把換到的位置后，后三位仍然是個(gè)降序的排列。 Next Permutation Implement next permutation, which rearranges numbers into the lexicogr...

    young.li 評(píng)論0 收藏0

  • [Leetcode]PermutationsI II Next Permutation Permut

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

    ChristmasBoy 評(píng)論0 收藏0

  • 31. Next Permutation

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

    denson 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<