[Leetcode] Permutation Sequence 全排列序列

testHs 发布于2019-08-14 12:34 / 364人阅读

摘要：找规律复杂度时间空间思路由于我们只要得到第个全排列，而不是所有全排列，我们不一定要将所有可能都搜索一遍。根据全排列顺序的性质，我们可以总结出一个规律假设全排列有个数组成，则第个全排列的第一位是。然后将得到，这个就是下一轮的。

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.

找规律 复杂度

时间 O(N) 空间 O(1)

思路

由于我们只要得到第K个全排列，而不是所有全排列，我们不一定要将所有可能都搜索一遍。根据全排列顺序的性质，我们可以总结出一个规律：假设全排列有n个数组成，则第k个全排列的第一位是k/(n-1)!。为了更形象一点，举例如下：

在这种情况下，第一个数字每2!=2个情况就改变一次，假设求第6个排列，我们先将其减1，方便整除运算，然后5/2=2。对于第一位，我们有三种可选数字1、2、3，所以5/2=2意味着我们选择第3个数字，也就是3（如果商是s，则选第s+1个数字）。然后将5%2得到1，这个1就是下一轮的k。

注意

这里有一个技巧，就是用一个列表将1到n存起来，每选用一个数就是移出那个数，就能保证不选重复数字的同时，其顺序也是一样的。

代码

public class Solution {

    public String getPermutation(int n, int k) {
        int mod = 1;
        List candidates = new ArrayList();
        // 先得到n!和候选数字列表
        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);
            // 得到当前应选数字的序数
            int first = k / mod;
            // 得到用于计算下一位的k
            k = k % mod;
            sb.append(candidates.get(first));
            // 在列表中移出该数字
            candidates.remove(first);
        }
        return sb.toString();
    }
}

混合云私有云字符串全排列 java 全排列数列字符串全排列算法最快的全排列算法

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

转载请注明本文地址：https://www.ucloud.cn/yun/64559.html

leetcode60. Permutation Sequence

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

摘要：我们所找到的这个元素就是排序需要改变的第一个元素。然后我们选取一个刚好大于此元素的数，与当前元素进行替换。并对后面的所有元素重新按照升序排列就可以得到最终的答案。题目详情 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of...

binaryTree 2019-08-19 10:41 评论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
字符串的全排列

摘要：问题输入一个字符串按字典序打印出该字符串中字符的所有排列。如此递归处理，从而得到所有字符的全排列。记斐波那契数列的第位这件事为，则有。其中，表示去掉那个开头字符的剩余字符串的全排列。问题输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。地址：https://...

sunny5541 2019-08-23 11:38 评论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