leetcode60. Permutation Sequence

xiaokai 发布于2019-08-15 10:38 / 3070人阅读

摘要：题目要求假设按照题中给的排列组合的顺序，假设有个数字，返回第个排列组合的结果。最后在个位上，选择中的第一个。这时知道以第位为开头的结果值有此时第个结果集在该位上的选择为。依次往后类推，直至到最后一位。

题目要求

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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