给定 n 和 k，返回第 k 个排列序列
2022-09-02 03:08:23
集合 [1，2，3,...,n] 总共包含 n！唯一排列。
通过按顺序列出和标记所有排列，我们得到以下序列（即，对于n = 3）：
- "123"
- "132"
- "213"
- "231"
- "312"
- “321” 给定 n 和 k，返回第 k 个排列序列。
例如，给定 n = 3， k = 4， ans = “231”。
有多种解决方案。但是它们都使用阶乘或复杂度大于O（n），例如O（n！）。如果您使用阶乘并找到位置处的 k/（n-1）！ 数字，则当 n 较大（n = 100） 时，问题就来了。这里因为n很大，（n-1）！溢出并变为 0。结果，我得到了一个除以零的错误...任何解决方案或算法？
这是我的代码：
public class KthPermutation {
public String getPermutation(int n, int k) {
// initialize all numbers
ArrayList<Integer> numberList = new ArrayList<Integer>();
for (int i = 1; i <= n; i++) {
numberList.add(i);
}
int fact = 1; // set factorial of n-1
for (int i = 1; i <= n-1; i++) {
fact = fact * i;
}
if ((long) k > (long) fact * n) {
k = (int) ((long) k - (long) (fact * n));
}
k--; // set k to base 0
StringBuilder result = new StringBuilder();
result = getP(result, numberList, n, k, fact);
return result.toString();
}
public static StringBuilder getP(StringBuilder result,
ArrayList<Integer> numberList, int n, int k, int fact) {
if (numberList.size() == 1 || n == 1) {
result.append(numberList.get(0));
return result; // return condition
}
int number = (k / fact) + 1 ;
result.append(numberList.get(number - 1));
numberList.remove(number - 1);
k = k % fact; // update k
fact = fact / (n - 1);
n--;
return getP(result, numberList, n, k, fact);
}
}
