“给定n和k,返回第k个排列。”
题目链接:
来源:力扣(LeetCode)
链接:60. 排列序列 - 力扣(LeetCode) (leetcode-cn.com)
给出集合 [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"
这个题对于给定的n和k,需要知道从左往右第k个排列中的每个位置的元素是什么。
首先求出第k个排列的首个元素,然后向下取整。
根据相似的思路,确定下一个元素。
代码参考:
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;
}
}
}
}
时间复杂度 : O(n2)
其中n是数组的长度,只需要遍历一遍数组即可求得答案。
空间复杂度: O(1)
只需要常数级别的空间存放变量。
不要回溯,容易超时,可以通过数学的方法解决,其实就是不断缩小范围。