leetcode 60 permutation-sequence 的问题

这道题先贴上答案吧

1. public String getPermutation(int n, int k) {
   
2.         List<Integer> res = new ArrayList<>();
   
3.         for(int i = 1; i <= n; i++) {
   
4.             res.add(i);
   
5.         }
   
6.         
   
7.         int[] fact = new int[n];
   
8.         fact[0] = 1;
   
9.         for(int i = 1; i < n; i++) {
   
10.             fact[i] = fact[i - 1] * i;
    
11.         }
    
12.         StringBuilder sb = new StringBuilder();
    
13.         for(int i = n; i > 0; i--) {
    
14.             int index = k/fact[i - 1];
    
15.             k = k%fact[i - 1];
    
16.             sb.append(res.get(index));
    
17.             res.remove(index);
    
18.         }
    
19.         return sb.toString();
    
20.     }

复制代码

完全想不通为啥k一定要等于k - 1..是因为res的原因吗？

直接用DFS求出第k个排列会超时。
因为原序列已排序且没有重复元素，所以找到第k个排列数可以不用DFS，直接找到每一位数的值。当序列元素为[1, n]时，当确定了头m个数时有(n - m)!种排列，如n = 9且k = 136371时，当确定了第一个数后，还有8!种排列，而由于136371 = 8! + 8! + 8! + 15411，所以可以确定第一个数为4。当确定了两个数后，还有7!种排列，由于15411 = 7! + 7! + 7! + 291，因此可以确定第二个数为5，注意此时4已经用掉了。如此继续下去，直到确定所有数字。