[Leetcode] Permutation Sequence 全排列序列

testHs 發(fā)布于2019-08-14 12:34 / 510人閱讀

摘要：找規(guī)律復雜度時間空間思路由于我們只要得到第個全排列，而不是所有全排列，我們不一定要將所有可能都搜索一遍。根據(jù)全排列順序的性質(zhì)，我們可以總結出一個規(guī)律假設全排列有個數(shù)組成，則第個全排列的第一位是。然后將得到，這個就是下一輪的。

Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):
"123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.

找規(guī)律 復雜度

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

思路

由于我們只要得到第K個全排列，而不是所有全排列，我們不一定要將所有可能都搜索一遍。根據(jù)全排列順序的性質(zhì)，我們可以總結出一個規(guī)律：假設全排列有n個數(shù)組成，則第k個全排列的第一位是k/(n-1)!。為了更形象一點，舉例如下：

在這種情況下，第一個數(shù)字每2!=2個情況就改變一次，假設求第6個排列，我們先將其減1，方便整除運算，然后5/2=2。對于第一位，我們有三種可選數(shù)字1、2、3，所以5/2=2意味著我們選擇第3個數(shù)字，也就是3（如果商是s，則選第s+1個數(shù)字）。然后將5%2得到1，這個1就是下一輪的k。

注意

這里有一個技巧，就是用一個列表將1到n存起來，每選用一個數(shù)就是移出那個數(shù)，就能保證不選重復數(shù)字的同時，其順序也是一樣的。

代碼

public class Solution {

    public String getPermutation(int n, int k) {
        int mod = 1;
        List candidates = new ArrayList();
        // 先得到n!和候選數(shù)字列表
        for(int i = 1; i <= n; i++){
            mod = mod * i;
            candidates.add(i);
        }
        // 將k先減1方便整除
        k--;
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n ; i++){
            mod = mod / (n - i);
            // 得到當前應選數(shù)字的序數(shù)
            int first = k / mod;
            // 得到用于計算下一位的k
            k = k % mod;
            sb.append(candidates.get(first));
            // 在列表中移出該數(shù)字
            candidates.remove(first);
        }
        return sb.toString();
    }
}

云服務器 GPU云服務器字符串全排列 java 全排列數(shù)列字符串全排列算法最快的全排列算法

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

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

leetcode60. Permutation Sequence

摘要：題目要求假設按照題中給的排列組合的順序，假設有個數(shù)字，返回第個排列組合的結果。最后在個位上，選擇中的第一個。這時知道以第位為開頭的結果值有此時第個結果集在該位上的選擇為。依次往后類推，直至到最后一位。題目要求 The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling...

xiaokai 2019-08-15 10:38 評論0 收藏0
leetcode 31 Next Permutation

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

binaryTree 2019-08-19 10:41 評論0 收藏0
[Leetcode] Next Permutation 下一個排列

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

young.li 2019-08-14 12:34 評論0 收藏0
字符串的全排列

摘要：問題輸入一個字符串按字典序打印出該字符串中字符的所有排列。如此遞歸處理，從而得到所有字符的全排列。記斐波那契數(shù)列的第位這件事為，則有。其中，表示去掉那個開頭字符的剩余字符串的全排列。問題輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。地址：https://...

sunny5541 2019-08-23 11:38 評論0 收藏0
leetcode46 Permutation 排列組合

摘要：題目要求也就是得出所有可能的排列組合結果解題思路和代碼這題顯然采用遞歸的思路。在這里，我采用實現(xiàn)隊列，從隊列頭獲得上一組的結果，和當前元素結合之后，將結果插入到隊尾。題目要求 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