[Leetcode] Next Permutation 下一個排列

young.li 發布于2019-08-14 12:34 / 2146人閱讀

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

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

升序倒置法 復雜度

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

思路

首先我們來思考下，什么是next permutation
比如124651這個序列，我們如果只想它變大一點點，應該盡可能的不去增加高位。因為增加高位會帶來更大的增益。所以對于一個長為n的序列，我們增加第n位的前提是，前n-1位已經達到了最大排列方法。所以我們從后往前看：

1
51
651

前面三位已經是各自最大的情況，不可能再變大，而到萬位的時候4651，可以將4移到后面來來增大。但是問題在于，把誰移到4的位置。因為是找下一個數，所以我們要找一個比4小卻盡可能大的數，所以找到5。把5換到4的位置后，后三位仍然是個降序的排列。然而這時候，因為已經將萬位增大了，我們要將前三位盡可能的變小，做成一個以5開頭最小的序列，而這個序列應該是升序的，所以我們直接把后三位倒置一下，就從降序變成升序了。

注意

找第一個下降點的循環和著第一個比下降點稍大的數的循環，其判斷條件都要包含=

代碼

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

GPU云服務器云服務器 Permutation 下一個節點 LeetCode 抖音自動播放下一個視頻

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

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

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

hedzr 2019-08-16 10: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
[Leetcode] Permutation Sequence 全排列序列

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

testHs 2019-08-14 12:34 評論0 收藏0
leetcode46 Permutation 排列組合

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

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