美文网首页ACM题库~
LeetCode 60. Permutation Sequenc

LeetCode 60. Permutation Sequenc

作者: 关玮琳linSir | 来源:发表于2017-09-26 17:05 被阅读12次

    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 th, return the kth permutation sequence.

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

    我刚开始尝试着把,所有的全排列都列出来,然后,找到对应位置的内容,但是这样效率太低,直接超时了,上网差了一下,和数学有关系。。。这题打算先放一放,放一下别人的代码吧。

    public String getPermutation(int n, int k) {
                char[] nums = new char[]{'1','2','3','4','5','6','7','8','9'};
                String tmp = "";
                for(int i=0;i<n;i++) {
                    tmp += nums[i];
                }
                StringBuffer s = new StringBuffer(tmp);
                String r = "";
                while(k>0&&!s.toString().equals("")) {
                    // 计算 (n-1)的排列个数cnt
                    int cnt = 1, i = s.length()-1;
                    while(i > 1) {
                        cnt*=i;
                        i-=1;
                    }
                    int pos = (k-1)/cnt;
                    r += s.charAt(pos);
                    s = s.deleteCharAt(pos);
                    k -= pos * cnt;
                }
                return r;
            }
    

    相关文章

      网友评论

        本文标题:LeetCode 60. Permutation Sequenc

        本文链接:https://www.haomeiwen.com/subject/kateextx.html