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 <= 9
- 1 <= k <= n!
分析：
-
面对这道算法题目，二当家的再次陷入了沉思。
-
如果模拟，按顺序生成k个序列，那效率实在太低了。
-
需要找到规律，直接去生成结果，这时候要用到一点数学知识，不是高数哈，是排列组合的知识，应该是高中的知识吧，也有可能是初中的，总之你肯定知道：
n个元素排列，排列的总数为n!。
…
-
可以推出如果有
n个元素排列，那么第一个位置会在(n - 1)!次排列后换下一个元素。 -
比如
4个元素[1, 2, 3, 4]排列，第一个位置先是1，会在3 * 2 * 1个排列（也就是3个元素排列的总数3!）之后，第一个位置开始排2，即：- 1234
- 1243
- 1324
- 1342
- 1423
- 1432
2134
…
-
所以我们可以直接用
(k - 1) / (n - 1)! + 1来计算第一个位置是第几个元素。 -
而接下来计算第二个位置的元素其实也是同计算第一个位置的元素是相似的，唯一的不同就是第一个位置的元素已经被占用了，所以后面要排除掉，因此要记录下哪个元素用过，哪个元素没有用过，后面就都是相同的子问题了。
题解：
rust：
impl Solution {
pub fn get_permutation(n: i32, k: i32) -> String {
let n = n as usize;
let mut k = k as usize;
// 结果
let mut ans = String::new();
// 阶乘缓存不同排列数
let mut factorial = vec![0; n];
factorial[0] = 1;
(1..n).for_each(|i| {
factorial[i] = factorial[i - 1] * i;
});
// 排列从0编号，便于后面计算
k -= 1;
// 1为有效还没有占用，0为无效已经被占用
let mut valid = vec![1; n + 1];
(1..n + 1).for_each(|i| {
// 计算当前位置的数字是第几个没被占用的数字
let mut order = k / factorial[n - i] + 1;
for j in 1..n + 1 {
// 取得数字
order -= valid[j];
if order == 0 {
ans.push((j as u8 + b'0') as char);
valid[j] = 0;
break;
}
}
// 余数为下级子排列的序号
k %= factorial[n - i];
});
return ans;
}
}
go：
func getPermutation(n int, k int) string {
// 结果
ans := ""
// 阶乘缓存不同排列数
factorial := make([]int, n)
factorial[0] = 1
for i := 1; i < n; i++ {
factorial[i] = factorial[i-1] * i
}
// 排列从0编号，便于后面计算
k--
// 1为有效还没有占用，0为无效已经被占用
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
}
c++：
class Solution {
public:
string getPermutation(int n, int k) {
// 结果
string ans;
// 阶乘缓存不同排列数
vector<int> factorial(n);
factorial[0] = 1;
for (int i = 1; i < n; ++i) {
factorial[i] = factorial[i - 1] * i;
}
// 排列从0编号，便于后面计算
--k;
// 1为有效还没有占用，0为无效已经被占用
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;
}
};
python：
class Solution:
def getPermutation(self, n: int, k: int) -> str:
# 结果
ans = list()
# 阶乘缓存不同排列数
factorial = [1]
for i in range(1, n):
factorial.append(factorial[-1] * i)
# 排列从0编号，便于后面计算
k -= 1
# 1为有效还没有占用，0为无效已经被占用
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)
java：
class Solution {
public String getPermutation(int n, int k) {
// 结果
final StringBuilder ans = new StringBuilder();
// 阶乘缓存不同排列数
final int[] factorial = new int[n];
factorial[0] = 1;
for (int i = 1; i < n; ++i) {
factorial[i] = factorial[i - 1] * i;
}
// 排列从0编号，便于后面计算
--k;
// 1为有效还没有占用，0为无效已经被占用
final 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();
}
}
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~