本文共 2515 字，大约阅读时间需要 8 分钟。

Permutation Sequence

题目

题目链接：

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 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.
• Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3Output: "213"

Example 2:

Input: n = 4, k = 9Output: "2314"

分析

对于数组[1, .., n]，其全排列共有n!中。现在给出n和k。其中n表示总共有多少个数（$1⩽n⩽9$）。k表示第几个排列（$1⩽k⩽n!$）。

其中，排列按照从小到大的顺序排序。

可能会有人使其第一个排列为12..n。然后不断循环求出下一个排列。直到第k个排列时停止。

但是这个方法时间复杂度很高，为$O(n!)$。虽然题目中n取值最大为9，此时n!为362880。也不是很大。但是如果这道题不是对数字而是对char字符进行排列。这种方法就行不通了。

其实，我们可以直接根据给出的k，计算出位置i是剩下的数字中排第几的。然后根据计算结果，组合n个字符即可。

下面对这个方法的合理性进行说明。 第1个位置一共有n种取法。第2个位置只能从剩下的n - 1个数字取一个，因此只能有n - 1种取法。依次类推，第n个数字只能有1种取法。 第1个位置确定后，其后面总共有(n - 1)!总可能。 由于排列结果是从小到大进行排序的。令m[i] = (n - i)!，i表示第几个位置。那么第1个位置取1时，1 <= k <= m[1]；取2时，1 * m[1] + 1<= k <= 2 * m[1]。以此类推，取n时，(n - 1) * m[1] + 1 <= k <= n * m[1]。 因此，我们可以从第一个位置开始。求出第i个位置是剩下的数字中的第几个数字pos[i]，然后更新k的值。 最后，模拟取数的过程，构建出结果字符串。 需要注意的是，pos[i]是剩下的数字中的第pos[i]个，而不是0到n中的第pos[i]个。

例如：对于n = 4，k = 9的情况。

位置	1	2	3	4
第几个	2	2	1	1
对应的值	2	3	1	4

说明：

对于第一个位置，剩下的数字为[1,2,3,4]，每个取法共有3! = 6种情况。因此，第一个位置取剩下数字中的2个数字，就是2。k更新为9 - 6 = 3。 对于第二个位置，剩下的数字为[1,3,4]，每个取法共有2! = 2种情况。因此，第二个位置取剩下数字的第2个数字，也就是3。k更新为3 - 2 = 1。 对于第三个位置，剩下的数字为[1, 4]，每个取法共有1种情况。因此，第3个位置取剩下数字的第一个数字，也就是1。 对于第4个位置，只能取剩下的那个数字，也就是4。

代码如下

class Solution {
       public String getPermutation(int n, int k) {
       	// sum[i]表示(i + 1)个数时共有多少种组合    	int[] sum = new int[n];    	// 表示每个位置的字符 chars[i]表示数字 (i + 1)    	char[] chars = new char[n];    	// pos[i]表示第i个位置的数是从剩下的数中的第pos[i]个。    	int[] pos = new int[n];    	sum[0] = 1;    	chars[0] = '1';    	StringBuilder result = new StringBuilder(n);    	// 初始化字符    	for (int i = 1; i < n; i++) {
       		sum[i] = sum[i - 1] * (i + 1);    		chars[i] = (char)('1' + i);    	}    	// 求出是第几个数    	for (int i = 0, j = n - 1; i < n - 1; i++, j--) {
       		pos[i] = (k - 1) / sum[j - 1];			k = k - pos[i] * sum[j - 1];    	}    	// 根据pos构建结构字符串    	for (int i = 0; i < n; i++) {
       		int num = pos[i];    		for (int j = 0; j < n; j++) {
       			if (chars[j] != ' ') {
       				if (num == 0) {
       					result.append(chars[j]);    					chars[j] = ' ';    					break;    				} else {
   						num--;					}    			}    		}    	}    	        return result.toString();    }}

转载地址：http://cibmb.baihongyu.com/