<option id="mm6u0"></option>

leetcode60. Permutation Sequence

xiaokai 發布于2019-08-15 10:38 / 3074人閱讀

摘要：題目要求假設按照題中給的排列組合的順序，假設有個數字，返回第個排列組合的結果。最后在個位上，選擇中的第一個。這時知道以第位為開頭的結果值有此時第個結果集在該位上的選擇為。依次往后類推，直至到最后一位。

題目要求

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):

1."123"
2."132"
3."213"
4."231"
5."312"
6."321"
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

假設按照題中給的排列組合的順序，假設有1~n個數字，返回第k個排列組合的結果。

思路與代碼

首先來整理一下思路。如果有n個數組，則能排列組合出n！個結果。然后再按照排列組合結果的各個位上的數字選擇來分析。這里舉一個具體的例子。就看題中給的例子，此時n=3。假設k=5。則在百位上，選擇的數字為[1，2，3]中的第三個，這是再看十位上的數字，選擇了[1,2]中的第一個數。最后在個位上，選擇[1]中的第一個。
可以總結出，假設輸入n，k，則結果上的從左往右第1位上的數字為結果集中第(k-1)/(n-1)!個數字。這時知道以第1位為開頭的結果值有(n-1)!,此時第k個結果集在該位上的選擇為k%factorial[n-1]。依次往后類推，直至到最后一位。代碼如下：

    public String getPermutation(int n, int k) {
        //factorial
        int[] factorial = new int[]{1,1,2,6,24,120,720,5040,40320,362880};
        
        //初始化
        List numbers = new LinkedList();
        for(int i = 0 ; i

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 Sequence Permutation Leetcod LeetCode

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

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

[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
leetcode78. Subsets

摘要：題目要求類似的題目有可以參考這篇博客可以參考這篇博客思路一遞歸還是利用遞歸的方式，在前一種情況的基礎上遍歷下一輪的組合情況。題目要求 Given a set of distinct integers, nums, return all possible subsets. Note: The solution set must not contain duplicate subset...

Rocko 2019-08-15 10:43 評論0 收藏0
[LeetCode] 953. Verifying an Alien Dictionary

Problem In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters. Given a seque...

ghnor 2019-08-16 13:57 評論0 收藏0
[LintCode] Permutation Sequence

摘要：做法先把這個數放入一個數組里，同時計算出的階乘。假設這一組是第組，第一個數就是，同時刪去這個數，并讓除以取余作為新的。如此循環，這樣，下一組的成員數減少了，要找的位置也更為精確了。 Problem Given n and k, return the k-th permutation sequence. Example For n = 3, all permutations are li...

Jacendfeng 2019-08-14 15:19 評論0 收藏0
[Leetcode] Palindrome Permutation 回文變換

摘要：最笨的方法就是用的解法，找出所有的，然后再用中判斷回文的方法來判斷結果中是否有回文。而中心對稱點如果是字符，該字符會是奇數次，如果在兩個字符之間，則所有字符都是出現偶數次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...

svtter 2019-08-14 12:36 評論0 收藏0