文章目录题目标题和出处难度题目描述要求示例数据范围解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析题目标题和出处标题排列序列出处60. 排列序列难度8 级题目描述要求集合[1, 2, 3, ..., n] \texttt{[1, 2, 3, ..., n]}[1, 2, 3, ..., n]共有n! \texttt{n!}n!种排列。按大小顺序列出所有排列情况并编号当n 3 \texttt{n 3}n 3时所有排列如下123 \texttt{123}123132 \texttt{132}132213 \texttt{213}213231 \texttt{231}231312 \texttt{312}312321 \texttt{321}321给定n \texttt{n}n和k \texttt{k}k返回第k \texttt{k}k个排列。示例示例 1输入n 3, k 3 \texttt{n 3, k 3}n 3, k 3输出213 \texttt{213}213示例 2输入n 4, k 9 \texttt{n 4, k 9}n 4, k 9输出2314 \texttt{2314}2314示例 3输入n 3, k 1 \texttt{n 3, k 1}n 3, k 1输出123 \texttt{123}123数据范围1 ≤ n ≤ 9 \texttt{1} \le \texttt{n} \le \texttt{9}1≤n≤91 ≤ k ≤ n! \texttt{1} \le \texttt{k} \le \texttt{n!}1≤k≤n!解法一思路和算法为了得到长度为n nn的第k kk个排列需要从左到右依次得到第k kk个排列的每一位上的数字。用index \textit{index}index表示排列的下标0 ≤ index n 0 \le \textit{index} n0≤indexn。当遍历到排列的第index \textit{index}index位时排列的下标范围[ 0 , index ] [0, \textit{index}][0,index]中的每一位已经确定对于第index \textit{index}index位的每个取值剩余的n − 1 − index n - 1 - \textit{index}n−1−index位的排列数是( n − 1 − index ) ! (n - 1 - \textit{index})!(n−1−index)!。利用该性质可以计算第k kk个排列的每一位上的数字。当index 0 \textit{index} 0index0时排列的第0 00位有n nn个取值每个取值对应的其余n − 1 n - 1n−1位的排列数是( n − 1 ) ! (n - 1)!(n−1)!。为了确定第k kk个排列的第0 00位的取值需要找到整数x xx满足( x − 1 ) × ( n − 1 ) ! k ≤ x × ( n − 1 ) ! (x - 1) \times (n - 1)! k \le x \times (n - 1)!(x−1)×(n−1)!k≤x×(n−1)!则第k kk个排列的第0 00位的取值是x xx。记count ( n − 1 ) ! \textit{count} (n - 1)!count(n−1)!用i ii表示排列的第0 00位的取值对于从1 11到n nn的每个整数i ii当k count k \textit{count}kcount时将k kk的值减count \textit{count}count直到k ≤ count k \le \textit{count}k≤count时i ii即为第k kk个排列的第0 00位的取值将i ii添加到排列的末尾。当index 0 \textit{index} 0index0时可以使用同样的方法得到第k kk个排列的第index \textit{index}index位的取值但是需要跳过已经使用的数字确保排列中的每个数字各不相同。可以使用回溯得到第k kk个排列。回溯的终止条件是index n \textit{index} nindexn此时得到第k kk个排列的每一位上的数字直接返回。当index n \textit{index} nindexn时使用上述做法得到排列的第index \textit{index}index位的取值并添加到排列的末尾然后对下标index 1 \textit{index} 1index1继续回溯。实现方面有以下两点说明。计算过程中需要使用到阶乘因此可以事先计算从0 00到n nn的每个整数的阶乘。为了确保排列中的每个数字各不相同需要使用哈希集合或数组存储已经使用的数字。对于每个下标需要遍历从1 11到n nn的每个整数如果整数i ii已经使用则跳过整数i ii。代码classSolution{intn,k;StringBuffertempnewStringBuffer();int[]factorials;boolean[]used;publicStringgetPermutation(intn,intk){this.nn;this.kk;this.factorialsnewint[n1];factorials[0]1;for(inti1;in;i){factorials[i]factorials[i-1]*i;}this.usednewboolean[n1];backtrack(0);returntemp.toString();}publicvoidbacktrack(intindex){if(indexn){return;}intcountfactorials[n-1-index];for(inti1;in;i){if(!used[i]){if(kcount){k-count;}else{temp.append(i);used[i]true;backtrack(index1);break;}}}}}复杂度分析时间复杂度O ( n 2 ) O(n^2)O(n2)其中n nn是排列的长度。计算阶乘需要O ( n ) O(n)O(n)的时间生成排列时的计算次数是O ( n 2 ) O(n^2)O(n2)因此时间复杂度是O ( n 2 ) O(n^2)O(n2)。空间复杂度O ( n ) O(n)O(n)其中n nn是排列的长度。存储当前排列的临时字符串、阶乘数组、哈希集合和递归调用栈需要O ( n ) O(n)O(n)的空间。解法二思路和算法也可以将递归回溯改成迭代实现省略递归调用栈空间。对于0 ≤ index n 0 \le \textit{index} n0≤indexn在生成排列的第index \textit{index}index位时执行如下操作。记count ( n − 1 − index ) ! \textit{count} (n - 1 - \textit{index})!count(n−1−index)!。对于从1 11到n nn的每个整数i ii如果整数i ii已经使用则跳过如果整数i ii尚未使用则执行如下操作。如果k count k \textit{count}kcount则将k kk的值减count \textit{count}count。如果k ≤ count k \le \textit{count}k≤count则i ii为第k kk个排列的第index \textit{index}index位的取值将i ii添加到排列的末尾。遍历结束时即可得到第k kk个排列。代码classSolution{publicStringgetPermutation(intn,intk){StringBuffertempnewStringBuffer();int[]factorialsnewint[n1];factorials[0]1;for(inti1;in;i){factorials[i]factorials[i-1]*i;}boolean[]usednewboolean[n1];for(intindex0;indexn;index){intcountfactorials[n-1-index];for(inti1;in;i){if(!used[i]){if(kcount){k-count;}else{temp.append(i);used[i]true;break;}}}}returntemp.toString();}}复杂度分析时间复杂度O ( n 2 ) O(n^2)O(n2)其中n nn是排列的长度。计算阶乘需要O ( n ) O(n)O(n)的时间生成排列时的计算次数是O ( n 2 ) O(n^2)O(n2)因此时间复杂度是O ( n 2 ) O(n^2)O(n2)。空间复杂度O ( n ) O(n)O(n)其中n nn是排列的长度。存储当前排列的临时字符串、阶乘数组和哈希集合需要O ( n ) O(n)O(n)的空间。