国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

leetcode 31 Next Permutation

binaryTree / 816人閱讀

摘要:我們所找到的這個元素就是排序需要改變的第一個元素。然后我們選取一個剛好大于此元素的數,與當前元素進行替換。并對后面的所有元素重新按照升序排列就可以得到最終的答案。

題目詳情
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.

題目的意思是找到當前元素排列的‘下一個排列’。那么什么叫‘下一個排列呢’?這里舉個例子,比如說元素1,2,3。它們的全排列是‘1,2,3’,‘1,3,2’,‘2,1,3’,‘2,3,1’,‘3,1,2’,‘3,2,1’因此比如求‘123’的下一個排列,就應該返回‘1,3,2’.
如果當前的序列不存在‘下一個排列’,那么就返回完全升序的第一個排列。

例子: 左側一列是輸入,右側是正確的輸出:
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

想法

當我們要求一個排列的‘下一個排列’,我們需要意識到問題的關鍵在于從數組末端遍歷到的,第一個不滿足nums[i] <= nums[i+1]條件的元素。

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

然后我們選取一個剛好大于此元素的數,與當前元素進行替換。并對后面的所有元素重新按照升序排列就可以得到最終的答案。

我描述的不是很清晰,這里引用一張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;
    }

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

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

相關文章

  • leetcode31 Next Permutation

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

    hedzr 評論0 收藏0
  • 31. Next Permutation

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

    未東興 評論0 收藏0
  • [Leetcode] Next Permutation 下一個排列

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

    young.li 評論0 收藏0
  • [Leetcode]PermutationsI II Next Permutation Permut

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

    ChristmasBoy 評論0 收藏0
  • 31. Next Permutation

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

    denson 評論0 收藏0

發表評論

0條評論

binaryTree

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<