class Solution {
public:
string getPermutation(int n, int k) {
}
};
60. 排列序列
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"给定 n 和 k，返回第 k 个排列。
示例 1：
输入：n = 3, k = 3 输出："213"
示例 2：
输入：n = 4, k = 9 输出："2314"
示例 3：
输入：n = 3, k = 1 输出："123"
提示：
1 <= n <= 91 <= k <= n!原站题解
golang 解法, 执行用时: 1 ms, 内存消耗: 2.1 MB, 提交时间: 2024-04-20 16:20:34
func getPermutation(n int, k int) string {
factorial := make([]int, n)
factorial[0] = 1
for i := 1; i < n; i++ {
factorial[i] = factorial[i - 1] * i
}
k--
ans := ""
valid := make([]int, n + 1)
for i := 0; i < len(valid); i++ {
valid[i] = 1
}
for i := 1; i <= n; i++ {
order := k / factorial[n - i] + 1
for j := 1; j <= n; j++ {
order -= valid[j]
if order == 0 {
ans += strconv.Itoa(j)
valid[j] = 0
break
}
}
k %= factorial[n - i]
}
return ans
}
java 解法, 执行用时: 1 ms, 内存消耗: 39.9 MB, 提交时间: 2024-04-20 16:20:20
class Solution {
public String getPermutation(int n, int k) {
int[] factorial = new int[n];
factorial[0] = 1;
for (int i = 1; i < n; ++i) {
factorial[i] = factorial[i - 1] * i;
}
--k;
StringBuffer ans = new StringBuffer();
int[] valid = new int[n + 1];
Arrays.fill(valid, 1);
for (int i = 1; i <= n; ++i) {
int order = k / factorial[n - i] + 1;
for (int j = 1; j <= n; ++j) {
order -= valid[j];
if (order == 0) {
ans.append(j);
valid[j] = 0;
break;
}
}
k %= factorial[n - i];
}
return ans.toString();
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 7 MB, 提交时间: 2024-04-20 16:20:06
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> factorial(n);
factorial[0] = 1;
for (int i = 1; i < n; ++i) {
factorial[i] = factorial[i - 1] * i;
}
--k;
string ans;
vector<int> valid(n + 1, 1);
for (int i = 1; i <= n; ++i) {
int order = k / factorial[n - i] + 1;
for (int j = 1; j <= n; ++j) {
order -= valid[j];
if (!order) {
ans += (j + '0');
valid[j] = 0;
break;
}
}
k %= factorial[n - i];
}
return ans;
}
};
python3 解法, 执行用时: 40 ms, 内存消耗: 14.8 MB, 提交时间: 2022-07-28 15:30:45
class Solution:
def getPermutation(self, n: int, k: int) -> str:
factorial = [1]
for i in range(1, n):
factorial.append(factorial[-1] * i)
k -= 1
ans = list()
valid = [1] * (n + 1)
for i in range(1, n + 1):
order = k // factorial[n - i] + 1
for j in range(1, n + 1):
order -= valid[j]
if order == 0:
ans.append(str(j))
valid[j] = 0
break
k %= factorial[n - i]
return "".join(ans)