LeetCode60-第k个排列

给出集合[1,2,3,…,n]，其所有元素共有n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当n = 3 时, 所有排列如下：

"123"

"132"

"213"

"231"

"312"

"321"

给定n 和k，返回第k个排列。

说明：

给定 n的范围是 [1, 9]。

给定 k 的范围是[1,n!]。

大致思路是根据k与总排列数(n!)的关系来推断出第k个排列，而不用依次求出排列直到第k个。

以每个数字开头的排列都有(n-1)!个，k/(n-1)!即可以求出字符串index为n-k-1处的字符。（注意字符串的index并非n-k，需要在开头加k--），以此类推更新k为除以(n-1)!所得的余数，更新n为n-1，再求下一位，直到n为1时终结。

如果使用递归则思路简单但很容易超时，基本也就是尾递归，用循环代替即可。

参考：https://blog.csdn.net/xiaoliucool1314/article/details/50777335

代码(java)：

class Solution{

    public string getPermutation(int n, int k){

        k--;

        List<Integer> nums = new ArrayList<>();

        for(int i = 1;i <= n;i++)

            nums.add(i);

        int fac = 1;

        for(int i = 2;i < n;i++)

            fac *= i;

        int count = n - 1;

        StringBuilder res = new StringBuilder();

        while(count >= 0){

            res.append(nums.remove(k / fac));

            k %= fac;

            if(count > 0)

                fac /= count;

            count--;

        }

        return res.toString();

    }

}