lintcode388. 第k个排列

亦凉 2023-07-07 12:55 30阅读 0赞

给定 n 和 k，求n的全排列中字典序第k个排列.

  1. 样例
  2. 样例 1:
  4. 输入: n = 3, k = 4
  5. 输出: "231"
  6. 解释: 
  7. n = 3时, 全排列如下:
  8. "123", "132", "213", "231", "312", "321"
  9. 样例 2:
  11. 输入: n = 1, k = 1
  12. 输出: "1"
  13. 挑战
  14. O(n*k)很容易, 你可以做到O(n^2n
  15. ​2
  16. ​​ )或更低的时间复杂度吗?
  18. 注意事项
  19. 1 ≤ n ≤ 9
  21. class Solution {
  23. public:
  24.     /**
  25.      * @param n: n
  26.      * @param k: the k th permutation
  27.      * @return: return the k-th permutation
  28.      */
  29.     string getPermutation(int n, int k) {
  31.         // write your code here
  32.         string start="123456789";
  33.         string res="";
  34.         vector<int> factor(n,1);
  35.         for (int i = 1; i < n; i++) {
  37.             factor[i]=factor[i-1]*i;
  38.         }
  39.         k--;
  40.         for (int i = n; i >= 1 ; i--) {
  42.             int index=k/factor[i-1];
  43.             k%=factor[i-1];
  44.             res.push_back(start[index]);
  45.             start.erase(index,1);
  46.         }
  47.         return res;
  48.     }
  49. };

发表评论

表情：
评论列表 （有 0 条评论，30人围观）

还没有评论，来说两句吧...

相关阅读