第k个排列
题目叙述:
给出集合 [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=1的时候会有1种情况，n=2会有2种情况，n=3会有6种情况，n=n会有(n!)种情况。当我们选择第k个序列的时候相当于我们的首位可以是第k/(n-1)!个数，依次第二位将是k%(n-1)!/(n-2)!个数······等等，因此我们将1~n用一个List集合存储起来，取出一个数后将其在List移出。直到List移空。时间复杂度为O(n)。
代码实现：
class Solution {
public String getPermutation(int n, int k) {
int[] nums = new int[n];
List<Integer> help = new ArrayList();
StringBuffer res=new StringBuffer();
int num = 1;
for (int i = 1; i < n+1; i++) {
num *= i;
nums[i - 1] = num;
help.add(i);
}
k--;
for (int i = n - 2; i > -1; i--) {
res.append(help.get(k/nums[i]));
help.remove(help.get(k/nums[i]));
k%=nums[i];
}
res.append(help.get(0));
return res.toString();
}
}
