给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3
输出: "213"
示例 2:
输入: n = 4, k = 9
输出: "2314"
本题为寻找n的全排列中第K个排列，n有n!个排列方式，那么n-1则有（n-1）个排列方式。
那么当以a1为第一个数的时候有n-1种排列方式。则第K个排列的第一个数为1-9中第(k/(n-1)!)+1个数。
例如，当n=4时可以有如下解释
我们实际上会产生如下四种情况：
1+permutation(2,3,4)1
2+permutation(1,3,4)
3+permutation(2,1,4)
4+permutation(2,3,1)
我们知道对于每种情况都会有(n-1)!种子集，对于上列来说就是6种子集。如果k=14的话，我们知道它一定在3+permutation(2,1,4)中，
并且是permutation(2,1,4)的第二个子集（14-12）=2，我们是按照例子中的index考虑，也就是数列从1开始。如果按照从0开始的话，
我们输入就要变成14-1=13）。我们看permutation(2,1,4)permutation(2,1,4)可以分为如下三种情况
1+permutation(2,4)
2+permutation(1,4)
4+permutation(2,1)
我们知道对于每种情况都会有(n-2)!种子集，对于上列来说就是2种子集。我们知道它一定是在1+permutation(2,4)中，并且是permutation(2,4)的第二个子集，
也就是(4,2)，所以最后的结果就是"3142"。我们可以非常轻松的得到如下递推公式
f(n,k)=n_list[k/(n−1)!]+f(n−1,k%(n−1)!)
其中n_list为[1，2，3，4，5，6，7，8，9]。
class Solution { public String getPermutation(int n, int k) { int[] factorial = new int[n]; factorial[0] = 1; for (int i = 1; i < n; ++i) { factorial[i] = factorial[i - 1] * i; } --k; StringBuffer ans = new StringBuffer(); int[] valid = new int[n + 1]; Arrays.fill(valid, 1); for (int i = 1; i <= n; ++i) { int order = k / factorial[n - i] + 1; for (int j = 1; j <= n; ++j) { order -= valid[j]; if (order == 0) { ans.append(j); valid[j] = 0; break; } } k %= factorial[n - i]; } return ans.toString(); } }
参考
1.leetcode 官方题解https://leetcode-cn.com/problems/permutation-sequence/solution/di-kge-pai-lie-by-leetcode-solution/