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.
Note:
- Given n will be between 1 and 9 inclusive.
- Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3Output: "213"
Example 2:
Input: n = 4, k = 9Output: "2314"
这道题是让求出n个数字的第k个排列组合，由于其特殊性，我们不用将所有的排列组合的情况都求出来，然后返回其第k个，我们可以只求出第k个排列组合即可，那么难点就在于如何知道数字的排列顺序，可参见网友，首先我们要知道当n = 3时，其排列组合共有3! = 6种，当n = 4时，其排列组合共有4! = 24种，我们就以n = 4, k = 17的情况来分析，所有排列组合情况如下：
1234
12431324134214231432213421432314 23412413243131243142321432413412 <--- k = 173421412341324213423143124321我们可以发现，每一位上1,2,3,4分别都出现了6次，当最高位上的数字确定了，第二高位每个数字都出现了2次，当第二高位也确定了，第三高位上的数字都只出现了1次，当第三高位确定了，那么第四高位上的数字也只能出现一次，下面我们来看k = 17这种情况的每位数字如何确定，由于k = 17是转化为数组下标为16：
最高位可取1,2,3,4中的一个，每个数字出现3！= 6次，所以k = 16的第一位数字的下标为16 / 6 = 2，在 "1234" 中即3被取出。这里我们的k是要求的坐标为k的全排列序列，我们定义 k' 为当最高位确定后，要求的全排序列在新范围中的位置，同理，k'' 为当第二高为确定后，所要求的全排列序列在新范围中的位置，以此类推，下面来具体看看：
第二位此时从1,2,4中取一个，k = 16，则此时的 k' = 16 % (3!) = 4，如下所示，而剩下的每个数字出现2！= 2次，所以第二数字的下标为4 / 2 = 2，在 "124" 中即4被取出。
3124
3142321432413412 <--- k' = 43421第三位此时从1,2中去一个，k' = 4，则此时的k'' = 4 % (2!) = 0，如下所示，而剩下的每个数字出现1！= 1次，所以第三个数字的下标为 0 / 1 = 0，在 "12" 中即1被取出。
3412 <--- k'' = 0
3421第四位是从2中取一个，k'' = 0，则此时的k''' = 0 % (1!) = 0，如下所示，而剩下的每个数字出现0！= 1次，所以第四个数字的下标为0 / 1= 0，在 "2" 中即2被取出。
3412 <--- k''' = 0
那么我们就可以找出规律了
a1 = k / (n - 1)!k1 = ka2 = k1 / (n - 2)!
k2 = k1 % (n - 2)!...an-1 = kn-2 / 1!
kn-1 = kn-2 % 1!an = kn-1 / 0!
kn = kn-1 % 0!
代码如下：
class Solution {public: string getPermutation(int n, int k) { string res; string num = "123456789"; vector f(n, 1); for (int i = 1; i < n; ++i) f[i] = f[i - 1] * i; --k; for (int i = n; i >= 1; --i) { int j = k / f[i - 1]; k %= f[i - 1]; res.push_back(num[j]); num.erase(j, 1); } return res; }};
类似题目：
参考资料：