问题描述
https://leetcode.com/problems/permutation-sequence/
解决思路一（Time Out）
先用递归，回溯，讲全排列集合写出来，然后再找到对应的第几个，转为String类型。
问题解惑
如何将List
代码
class Solution {
public String getPermutation(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if(n < 0 || k < 0) return " ";
int[] nums = new int[n];
for(int i = 0; i < n; i++){
nums[i] = i + 1;
}
helper(res, new ArrayList<>(), nums);
//convert List<Integer> to String
StringBuilder str = new StringBuilder();
Iterator<Integer> it = res.get(k - 1).iterator();
while(it.hasNext()){
str.append(it.next());
}
return str.toString();
}
public void helper(List<List<Integer>> res, List<Integer> list, int[] nums){
if(list.size() == nums.length){
res.add(new ArrayList<>(list));
return;
}
for(int i = 0; i < nums.length; i++){
if(list.contains(nums[i])) continue;
list.add(nums[i]);
helper(res, list, nums);
list.remove(list.size() - 1);
}
}
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)
解决思路二
将全排列划分组，相当于n分法来做，有点复杂，建议看basketwang的视频理解
问题解惑
为什么要k–？
因为下标是从0开始的，而k代表第几个，需要和下标统一，所以要先–。
代码
class Solution {
public String getPermutation(int n, int k) {
char[] res = new char[n];
List<Integer> nums = new ArrayList<>();
for(int i = 1; i <= n; i++){
nums.add(i);
}
k--;
for(int i = 0; i < n; i++){
res[i] = Character.forDigit(nums.remove(k / factorial(n -1 -i)), 10);
k = k % factorial(n - 1 -i);
}
return new String(res);
}
public int factorial(int n){
if(n == 0 || n == 1) return 1;
return factorial(n - 1) * n;
}
}
复杂度分析
- 时间复杂度：O(n!)
- 空间复杂度：O(n)
