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.
https://oj.leetcode.com/problems/permutation-sequence/
计算1~n数字的第k个排列
思路1：从小到大生成同时计数，直到第k个。 肯定超时试都不用试。。
思路2：直接根据规律计算第k个排列。
分析：1~n个数共有n!个排列，1开头的有(n-1)!个，2开头的(n-1)!个，...n开头的有(n-1)!个。因此用k/(n-1)!就确定了第一位数字，然后依次类推（用过的数字要去除），继续在(n-1)!个数中找第k%(n-1)!个数。
思路2代码：
public class Solution {
public String getPermutation(int n, int k) {
int[] num = new int[n];
int permSum = 1;
for (int i = 0; i < n; i++) {
num[i] = i + 1;
permSum *= (i + 1);
}
StringBuilder sb = new StringBuilder();
k--;//change to base 0
for (int i = 0; i < n; i++) {
permSum = permSum / (n - i);
int selected = k / permSum;
sb.append(num[selected]);
for (int j = selected; j < n - i - 1; j++)
num[j] = num[j + 1];
k = k % permSum;
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(new Solution().getPermutation(4, 10));
}
}
第二遍记录：
注意k每次的变化 k %=permProd;
注意每次选完一个元素后，数组后面的元素向前移动。移动之后被选择的数字被覆盖，数组最后一个元素舍弃。比如原来是[1,2,3,4,5]，3被选走了，数组变为[1,2,4,5,5]，最后一个5其实相当于被舍弃，之后只能从[1,2,4,5]中选下一次填充的数字。
public class Solution { public String getPermutation(int n, int k) { int[] num = new int[n]; int permProd = 1; for (int i = 0; i < n; i++) { num[i] = i + 1; permProd *= num[i]; } StringBuilder sb = new StringBuilder(); k--; int idx = 0; for (int i = 0; i < n; i++) { permProd /= n - i; idx = k / permProd; sb.append(num[idx]); // move the array after the index idx for (int j = idx; j < n - i - 1; j++) { num[j] = num[j + 1]; } k %= permProd; } return sb.toString(); } public static void main(String[] args) { System.out.println(new Solution().getPermutation(3, 6)); } }
参考：