原题地址（中等）

方法1—数学

经力扣评论区网友提醒，我这里所用的思路叫做逆康托展开

思路

利用排列组合的性质，对此题进行数学方面的分析，是可以得到解决的。

我们先讲一下排列组合相关的知识，来做一个思想上的铺垫。

  • n=8 时有多少种排列呢？我们都知道，有 n! 种排列，最小为 1,2,3,4,5,6,7,8 ，最大为 8,7,6,5,4,3,2,1 。
  • 那么当最高位的数固定为 1 时，有多少种排列呢？我们也很容易就得出来，是 (n-1)! 种排列，最小为1,2,3,4,5,6,7,8 ，最大为 1,8,7,6,5,4,3,2
  • 那么当最高位的数固定为 2 时，有多少种排列呢？还是 (n-1)! 种
  • 最高位为 1 对应的是第 1 种~第 (n-1)!=6 种排列，依次类推，最高位为 2 对应的是第 (n-1)!+1=7 种~第 2(n-1)!=12 种排列，最高位为 3 对应的是第 2``(n-1)!+1=13 种~第 3``(n-1)!=18 种排列。想必大家已经发现规律了，我们就借助这个规律来解题。

回到题目上来，我们怎么求出第 k 个排列？借助上面的思路，我们用一个递归的过程来求解，以 n=4 ,k=7 为例：

  • 固定最高位为 1 不变，有 (n-1)!=6 种排列，固定最高位为 2 不变，也有 (n-1)!=6 种排列，所以 k=7 一定是以 2 开头的。所以我们找到了最高位2。
  • 还剩3个数：1,3,4。更新 k -= 1*(n-1)!=3 ， n -= 1 。问题就变成了 nums=[1,3,4], k=3 。以同样的方法找当前最高位，为 1 。
  • 还剩2个数：3,4。更新 k -= 1*(n-1)! =1 ， n -= 1 ，问题就变成了 nums=[3,4], k=1 。

我说的有点啰嗦emmmm
实在看不懂的话照着下面代码模拟一遍流程就能懂了

代码

  1. class Solution {
  2. public:
  3.     int mul(int num){
  4.         // 返回num的阶乘
  5.         int ans = 1;
  6.         for(int i=1; i<=num; i++)   ans *= i;
  7.         return ans;
  8.     }
  10.     string getPermutation(int n, int k) {
  11.         vector<int> v;   // 存放当前的数字
  12.         for(int i=1; i<=n; i++)   v.push_back(i);
  13.         string ans = "";
  14.         while(n){
  15.             int cur_sum = mul(n-1);  //当前阶乘
  16.             // k-1是边界的一个处理，比如n=3,k=4时，因为用的是闭区间[]，不减一的话边界统一不起来，会成为[)
  17.             int t = (k-1) / cur_sum;  //当前最高位要填v[t]
  18.             ans += ('0'+v[t]);
  19.             v.erase(v.begin()+t);
  20.             k -= (t * cur_sum);
  21.             n--;
  22.         }
  23.         return ans;
  24.     }
  25. };

递归版：

  1. class Solution {
  2. public:
  3.     vector<int> v;
  4.     int* factorial;
  5.     string ans ;
  6.     void calFactorial(int n){
  7.         factorial = new int[n+1];
  8.         factorial[0] = 1;
  9.         for(int i=1; i<=n; i++)     factorial[i] = factorial[i-1] * i;
  10.     }
  12.     void dfs(int i, int n, int k){  //i表示为v的下标
  13.         if(v.empty())   return;
  14.         if(k >= 0 && k <= factorial[n-1]){
  15.             ans += '0'+v[i];
  16.             v.erase(v.begin()+i);
  17.             dfs(0, n-1, k);
  18.         }
  19.         else
  20.             dfs(i+1, n, k-factorial[n-1]);
  21.     }
  23.     string getPermutation(int n, int k) {
  24.         calFactorial(n);
  25.         for(int i=1; i<=n; i++)   v.push_back(i);
  26.         ans = "";
  28.         dfs(0, n, k);
  30.         return ans;
  31.     }
  32. };

时空复杂度

while循环里面套了一个求阶乘的函数，所以时间复杂度为 O(N^2)
空间复杂度为 O(N)