一、题目
1、算法题目
“给定n和k，返回第k个排列。”
题目链接：
来源：力扣（LeetCode）
链接：60. 排列序列 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123" "132" "213" "231" "312" "321"
给定 n 和 k，返回第 k 个排列。
示例 1： 输入： n = 3, k = 3 输出： "213" 复制代码
示例 2： 输入： n = 4, k = 9 输出： "2314" 复制代码
二、解题
1、思路分析
这个题对于给定的n和k，需要知道从左往右第k个排列中的每个位置的元素是什么。
首先求出第k个排列的首个元素，然后向下取整。
根据相似的思路，确定下一个元素。
2、代码实现
代码参考：
public class Solution { public int[] factor = new int[]{1,1,2,6,24,120,720,5040,40320,362880}; public string GetPermutation(int n, int k) { StringBuilder path = new StringBuilder(); bool[] visited = new bool[n + 1]; dfs(n, k, 0, visited, path); return path.ToString(); } private void dfs(int n, int k, int depth, bool[] visited, StringBuilder path){ if(depth == n){ return; } int fac = factor[n - 1 - depth]; for(int i = 1; i <= n; i++){ if(visited[i] == false){ //当k大于可生成的叶子节点数，剪枝 if(k > fac){ k -= fac; continue; } path.Append(i.ToString()); visited[i] = true; dfs(n, k, depth+1, visited, path); return; } } } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n2)
其中n是数组的长度，只需要遍历一遍数组即可求得答案。
空间复杂度： O(1)
只需要常数级别的空间存放变量。
三、总结
不要回溯，容易超时，可以通过数学的方法解决，其实就是不断缩小范围。
