Permutation Sequence

r囧r小猫 2023-06-10 03:22 12阅读 0赞

# Permutation Sequence #

### 文章目录 ###

*  Permutation Sequence
 *   *  题目
     *  分析
     *  代码如下

## 题目 ##

题目链接：[https://leetcode.com/problems/permutation-sequence/][https_leetcode.com_problems_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 = 3
    Output: "213"

**Example 2:**

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

## 分析 ##

对于数组`[1, .., n]`，其全排列共有`n!`中。现在给出`n`和`k`。其中`n`表示总共有多少个数（ 1 ⩽ n ⩽ 9 1 \\leqslant n \\leqslant 9 1⩽n⩽9）。`k`表示第几个排列（ 1 ⩽ k ⩽ n ! 1 \\leqslant k \\leqslant n! 1⩽k⩽n!）。  
其中，排列按照从小到大的顺序排序。

可能会有人使其第一个排列为`12..n`。然后不断循环求出下一个排列。直到第`k`个排列时停止。  
但是这个方法时间复杂度很高，为 O ( n ! ) O(n!) 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]`，每个取法共有`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();
        }
    }

[https_leetcode.com_problems_permutation-sequence]: https://leetcode.com/problems/permutation-sequence/