一开始想用permutations那种全排列来计算，DFS写了好久发现人家n可以是9位数，递归几千万次这得什么计算机做得到。。

DFS(只能计算n很小的情况。。不可行)

String res = "";public String getPermutation(int n, int k) {   int[] count = new int[1];   int[] num = new int[n];   for (int i = 0; i < n; i++) {      num[i] = i + 1;   }   backtracking(count, k, num, "", new boolean[num.length]);   return res; } private void backtracking(int[] count, int k, int[] nums, String item, boolean[] used) {   if (item.length() == nums.length) {      if (++count[0] == k) {         res = item;      }      return;   }   for (int i = 0; i < nums.length; i++) {      if (!used[i]) {         used[i] = true;         backtracking(count, k, nums, item + nums[i], used);         used[i] = false;      }   }}复制代码

数学方法：

每次计算最高位的数字，用一个数组保存剩下的数字。index代表剩下的数字的位置。 index计算的方法是： index = k / (n-1)! 这个index就表示，之前有index组个全排列（开头是同一个数字的一组全排列算是一组） k就减去之前index * (n-1)!那么多个排列，再循环计算新的index即可。

public String getPermutation(int n, int k) {		int[] factorial = new int[n];		factorial[0] = 1;		for (int i = 1; i < n; i++) {			//阶乘			factorial[i] = i * factorial[i - 1];		}		List
    
      nums = new ArrayList<>();		for (int i = 1; i <= n; i++) {			nums.add(i);		}		//k从0开始		k--;		StringBuilder res = new StringBuilder();		for (int i = 1; i <= n; i++) {			int index = k / factorial[n - i];			res.append(nums.remove(index));			k -= index * factorial[n - i];		}		return res.toString();	}复制代码