Description

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 for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Example

Input: n = 3, k = 3
Output: "213"

分析

     刚开始决定采用 next permutation 进行求解。 考虑到 next permutation 通常分为 2 个部分，第一步是将某个数替换前面第一个小于它的数，第二部是进行刚替换过数字右边数字的排序。
考虑到排序比较耗时，在求第 kth 的排序时，时间复杂度会变成 k * n log n 。决定采用预先计算的方式进行优化，比如知道， [k1th, k2th, k3th ....] 对应的排列组合， 找到第一个小于 kth
 的 kxth 排练组合，以此为基础进行计算。 想到这里，突然灵机一动。有了下面更好的优化

对于 n 个数的全排练 
 以 1 为开始数字的全排列有 (n-1) !
 以 2 为开始的有 （n-1）！
.........

假设 n 为 9， 现在计算 kth 开始的数字是以 5 为开始数字。 nkth 为  kth - 5 * 9 ！。 新的数字组合从 [1,2,3,4,   6,7,8,9] ， 以此类类推，计算 nkth 对应的组合数字！！

Tips

1 <= n <= 9
1 <= k <= n!

总结