BiliBili
YouTube
原题
中文
给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:
“123”
“132”
“213”
“231”
“312”
“321”
给定 n 和 k,返回第 k 个排列。
说明
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
英文
The set [1,2,3,...,n]
contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note:
- Given n will be between 1 and 9 inclusive.
- Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3 Output: "213"
Example 2:
Input: n = 4, k = 9 Output: "2314"
思路

代码
回溯
class Solution {
private:
bool helper(vector<int>& vis, vector<int>& result, int& no, int target) {
if (result.size() == vis.size()) {
if (++no == target) {
return true;
}
return false;
}
for (int i = 1; i <= vis.size(); ++i) {
if (vis[i - 1]) continue;
vis[i - 1] = 1;
result.push_back(i);
bool next = helper(vis, result, no, target);
if (next) return true;
result.pop_back();
vis[i - 1] = 0;
}
return false;
}
public:
string getPermutation(int n, int k) {
vector<int> vis(n, 0);
vector<int> result;
int no = 0;
helper(vis, result, no, k);
string ans;
for (auto n : result) {
ans += to_string(n);
}
return ans;
}
};
复杂度分析
时间复杂度:O(n!)
空间复杂度:O(n)
数学
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> fact(1, 1);
// 0 1 2 3 4 5 6 7 8 9
// 1 1 2 6 24 ......
for (int i = 1; i <= 9; ++i) {
fact.push_back(fact.back() * i);
}
string nums = "123456789";
string ans;
while (n > 0) {
int tmp = (k - 1) / fact[n - 1];
ans += nums[tmp];
nums.erase(nums.begin() + tmp);
k -= tmp * fact[n - 1];
--n;
}
return ans;
}
};
复杂度分析
时间复杂度:O(n)
空间复杂度:O(n)
参考
原题链接:https://leetcode.com/problems/permutation-sequence/
欢迎分享,引用。若转载,请联系我,谢谢配合。 本文地址:https://qoogle.top/leetcode-60-permutation-sequence/