LeetCode 60. 第k个排列 C#
原题链接
中等
作者:
hpstory
,
2022-08-05 00:02:02
,
所有人可见
,
阅读 127
C# 代码
// 按照顺序确认每一位的数值,当第i位确定时,后面的排列方式共有(n - i)!,比如n = 4, 第一个确认为1时,后面共有6种排列方式。
// 逐步比较k和(n - i)!,就可以获得结果。
public class Solution {
public string GetPermutation(int n, int k) {
string result = string.Empty;
// 可以预先保存所有需要使用的阶乘0~n - 1
int[] facts = new int[n];
facts[0] = 1;
// 保证每个数字只能使用一次
bool[] used = new bool[n + 1];
int fact = 1;
for (int i = 1; i < n; i++){
fact *= i;
facts[i] = fact;
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (!used[j]){
if (k > facts[n - i]){
k -= facts[n - i];
}
else{
result += j.ToString();
used[j] = true;
// 每次确定一位后就可以跳出循环, 找下一位数字
break;
}
}
}
}
return result;
}
}