本文共 2184 字，大约阅读时间需要 7 分钟。
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):1."123"2."132"3."213"4."231"5."312"6."321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
前面做过很多个这样类似题，所以很快就能想到找下一个字串。
public String getPermutation(int n, int k) { if (n == 1) return "1"; int[] nums = new int[n]; for (int i = 0; i < n; i++) nums[i] = i + 1; for (int i = 1; i < k; i++) { nums = getNextPermutation(nums); } String str = ""; for (int i = 0; i < nums.length; i++) { str += nums[i]; } return str; } public int[] getNextPermutation(int[] nums) { int i = nums.length - 1; while (i > 0 && nums[i] < nums[i - 1]) i--; int second = Integer.MAX_VALUE, secondIndex = Integer.MAX_VALUE; for (int j = nums.length - 1; j >= i; j--) if (nums[j] > nums[i - 1] && nums[j] < second) { second = nums[j]; secondIndex = j; } int temp = nums[i - 1]; nums[i - 1] = nums[secondIndex]; nums[secondIndex] = temp; Arrays.sort(nums, i, nums.length); return nums; } 虽然AC了，不过效率实在是很低，我又找到了一个效率很高的，beat88%的算法。
public String getPermutation(int n, int k) { StringBuilder sb = new StringBuilder(); boolean[] used = new boolean[n]; k = k - 1; int factor = 1; for (int i = 1; i < n; i++) { factor *= i; } for (int i = 0; i < n; i++) { int index = k / factor; k = k % factor; for (int j = 0; j < n; j++) { if (used[j] == false) { if (index == 0) { used[j] = true; sb.append((char) ('0' + j + 1)); break; } else { index--; } } } if (i < n - 1) { factor = factor / (n - 1 - i); } } return sb.toString(); } 转载地址：http://equio.baihongyu.com/