31. Next Permutation

denson 發布于2019-08-16 10:34 / 1439人閱讀

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

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
1,7,6,5,4,3 -> 3,1,4,5,6,7
7,6,5,8,3 ->  7,6,8,3,5

這里實際上是找下一個更大的數字。比如1,2,3 我們很容易知道下一個數字是1,3,2。
從尾到頭找，第一段ascending的部分出現。后面的部分就可以有更大的組合。

  i        
9 1 7 5 4 3
          j  
9 3 7 5 4 1
    i+1
9 3 1 4 5 7

  i
9 6 7 5 4 3
    j
9 7 6 5 4 3
    i+1
9 7 3 4 5 6

public class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length <= 1) return;
        
        int i = nums.length - 2;
        
        // 找到尾部的第一段遞減序列。
        while(i >= 0 && nums[i] >= nums[i+1]){
            i--;
        }
        
        if(i >= 0){
            int j = nums.length - 1;
            // 這里是在遞減序列中找到下一個比nums[i]大的數字，作為序列的頭。
            while(i < j && nums[j] <= nums[i]){
                j--;
            }
            swap(nums, i, j);
        }
        // 尾部的遞減序列變成遞增序列。
        reverse(nums, i+1, nums.length-1);
        
    }
    
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public void reverse(int[] nums, int i, int j){
        while(i < j){
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}

云服務器 GPU云服務器 Permutation -next Next next.js

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/70031.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
leetcode31 Next Permutation

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

hedzr 2019-08-16 10:34 評論0 收藏0
[LintCode] Next Permutation II [Next Permutation]

摘要：從末位向前遍歷，假設循環開始全是倒序排列，如當第一次出現正序的時候，如的和此時從數列末尾向前循環到，找到第一個比大的交換這兩個數，變成倒置第位到末位的數為正序排列這里的是完全倒置的排列，如，即上面循環的情況完全沒有出現， Problem Implement next permutation, which rearranges numbers into the lexicographic...

mikasa 2019-08-14 15:15 評論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