力扣算法题—060第K个排列

全栈程序员-用户IM • 2021年7月4日下午12:00 • 未分类

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"

给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。

示例 1:

输入: n = 3, k = 3
输出: "213"

示例 2:

输入: n = 4, k = 9
输出: "2314"

 1 #include "_000库函数.h"
 2 
 3 //一打眼看到题目描述，就想起用排列算法
 4 //时间有点长588ms
 5 
 6 class Solution {
 7 public:
 8     string getPermutation(int n, int k) {
 9         vector<int>v;
10         for (int i = 1; i <= n; ++i)
11             v.push_back(i);
12         --k;
13         while (next_permutation(v.begin(), v.end()) && --k);
14         string s = "";
15         for (auto a : v)
16             s += a + '0';
17         return s;
18     }
19 };
20 
21 //用一下递归
22 class Solution {
23 public:
24     string getPermutation(int n, int k) {
25         vector<int>v;
26         for (int i = 1; i <= n; ++i)
27             v.push_back(i);
28         Combin(v, 1, 0);
29         string s = "";
30         for (auto a : v)
31             s += a + '0';
32         return s;
33     }
34     void Combin(vector<int>&v, int k, int s) {
35         if (!k)return;
36         if (s >= v.size())--k;        
37         for (int i = s; i < v.size(); ++i) {
38             swap(v[i], v[s]);
39             Combin(v, k, s + 1);
40             swap(v[i], v[s]);
41         }
42     }
43 };
44     
45 //博客答案，没怎么看懂
46 //后期看懂再更新
47 //12ms
48 class Solution {
49 public:
50     string getPermutation(int n, int k) {
51         string res;
52         string num = "123456789";
53         vector<int> f(n, 1);
54         for (int i = 1; i < n; ++i) f[i] = f[i - 1] * i;
55         --k;
56         for (int i = n; i >= 1; --i) {
57             int j = k / f[i - 1];
58             k %= f[i - 1];
59             res.push_back(num[j]);
60             num.erase(j, 1);
61         }
62         return res;
63     }
64 };
65 
66 
67 void T060() {
68     Solution s;
69     cout << s.getPermutation(3, 3) << endl;
70     cout << s.getPermutation(4, 9) << endl;
71 }