本题也可以使用回溯,但耗时太久,这里介绍数学统计的方法
class Solution { public String getPermutation(int n, int k) { StringBuilder sb = new StringBuilder(); boolean[] st = new boolean[n+1]; // 记录每个使用过的数 for(int i = 0; i < n; i++) { // 确定每一位的数 int cnt = 1; for(int j = 2; j < n - i; j++) cnt *= j; // 计算到当前位共有多少个数,是个阶乘 // 从1 到 n确定当前位上的数 for(int j = 1; j <= n; j++) { if(!st[j]) { // 没被使用过 if(cnt < k) { k -= cnt; } else { sb.append(j); st[j] = true; break; // 找到就退出继续找下一位,每个位只有一个数 } } } } return sb.toString(); } }