Множество [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);
}
}
