题目是这样的:
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 (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
就是说,按字典序给出第k个排列。
因为之前做了“生成下一个排列”的题目,就直接拿过来用了。不料超时,于是只能用数学的方法做了。当然这也不是我想出来的,而是搜出来的(逃。。。)
基本的想法是,对于第k个排列,{a1, a2, a3, ..., an}, a1 是多少呢?
因为{a2, a3, ..., an} 一共有 (n-1)!种,a1在num中的index相当于 k / (n-1)!。换句话解释,就是一共有n个block,每个block大小是(n-1)!这么大,现在要求的就是在哪个block。
同理,求a2的时候,a1(在哪个block)已经求出来了,update k = k % (n-1)!, block的大小变成了(n-2)!, 这又是一个子问题了。
代码如下:
public String getPermutation(int n, int k) {
int[] num = new int[n];
int perNumCount = 1; for(int i = 0; i < n; i++) {
num[i] = i+1;
perNumCount *= i + 1;
}
k--;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; i++) {
perNumCount = perNumCount / (n - i);
int choosed = k / perNumCount;
sb.append(String.valueOf(num[choosed]));
for(int j = choosed; j < n - i - 1; j++) {
num[j] = num[j+1];
}
k = k % perNumCount;
}
return sb.toString();
}