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

資訊專欄INFORMATION COLUMN

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

young.li / 2171人閱讀

摘要：因?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 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
升序倒置法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

首先我們來(lái)思考下，什么是next permutation
比如124651這個(gè)序列，我們?nèi)绻幌胨兇笠稽c(diǎn)點(diǎn)，應(yīng)該盡可能的不去增加高位。因?yàn)樵黾痈呶粫?huì)帶來(lái)更大的增益。所以對(duì)于一個(gè)長(zhǎng)為n的序列，我們?cè)黾拥趎位的前提是，前n-1位已經(jīng)達(dá)到了最大排列方法。所以我們從后往前看：

1
51
651

前面三位已經(jīng)是各自最大的情況，不可能再變大，而到萬(wàn)位的時(shí)候4651，可以將4移到后面來(lái)來(lái)增大。但是問題在于，把誰(shuí)移到4的位置。因?yàn)槭钦蚁乱粋€(gè)數(shù)，所以我們要找一個(gè)比4小卻盡可能大的數(shù)，所以找到5。把5換到4的位置后，后三位仍然是個(gè)降序的排列。然而這時(shí)候，因?yàn)橐呀?jīng)將萬(wàn)位增大了，我們要將前三位盡可能的變小，做成一個(gè)以5開頭最小的序列，而這個(gè)序列應(yīng)該是升序的，所以我們直接把后三位倒置一下，就從降序變成升序了。

注意

找第一個(gè)下降點(diǎn)的循環(huán)和著第一個(gè)比下降點(diǎn)稍大的數(shù)的循環(huán)，其判斷條件都要包含=

代碼 
public class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length <= 1){
            return;
        }
        int i = nums.length - 2;
        // 找到第一個(gè)下降點(diǎn)，我們要把這個(gè)下降點(diǎn)的值增加一點(diǎn)點(diǎn)
        // 對(duì)于511這種情況，要把前面兩個(gè)1都跳過，所以要包含等于
        while(i >= 0 && nums[i] >= nums[i + 1]){
            i--;
        }
        // 如果這個(gè)下降點(diǎn)還在數(shù)組內(nèi)，我們找到一個(gè)比它稍微大一點(diǎn)的數(shù)替換
        // 如果在之外，說(shuō)明整個(gè)數(shù)組是降序的，是全局最大了
        if(i >= 0){
            int j = nums.length - 1;
            // 對(duì)于151，這種情況，要把最后面那個(gè)1跳過，所以要包含等于
            while(j > i && nums[j] <= nums[i]){
                j--;
            }
            swap(nums, i, j);
        }
        // 將下降點(diǎn)之前的部分倒序構(gòu)成一個(gè)最小序列
        reverse(nums, i + 1, nums.length - 1);
    }
    
    private void swap(int[] nums, int i, int j){
        int tmp = nums[j];
        nums[j] = nums[i];
        nums[i] = tmp;
    }
    
    private void reverse(int[] nums, int left, int right){
        while(left < right){
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

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

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

相關(guān)文章

  • leetcode 31 Next Permutation

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

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

  • 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

  • [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

  • [Leetcode] Permutation Sequence 全排列序列

    摘要：找規(guī)律復(fù)雜度時(shí)間空間思路由于我們只要得到第個(gè)全排列，而不是所有全排列，我們不一定要將所有可能都搜索一遍。根據(jù)全排列順序的性質(zhì)，我們可以總結(jié)出一個(gè)規(guī)律假設(shè)全排列有個(gè)數(shù)組成，則第個(gè)全排列的第一位是。然后將得到，這個(gè)就是下一輪的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...

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

  • leetcode46 Permutation 排列組合

    摘要：題目要求也就是得出所有可能的排列組合結(jié)果解題思路和代碼這題顯然采用遞歸的思路。在這里，我采用實(shí)現(xiàn)隊(duì)列，從隊(duì)列頭獲得上一組的結(jié)果，和當(dāng)前元素結(jié)合之后，將結(jié)果插入到隊(duì)尾。 題目要求 Given a collection of distinct numbers, return all possible permutations. For example, [1,2,3] have the ...

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

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

0條評(píng)論

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