LeetCode: Permutation Sequence 解题报告

时间:2022-06-15 20:55:37

Permutation Sequence

https://oj.leetcode.com/problems/permutation-sequence/

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth
permutation sequence.

Note: Given n will be between 1 and 9
inclusive.

解答:

1. 以某一数字开头的排列有(n-1)! 个。
例如: 123, 132, 以1开头的是 2!个
2. 所以第一位数字就可以用 (k-1) / (n-1)!  来确定
.这里K-1的原因是,序列号我们应从0开始计算,否则在边界时无法计算。
3. 第二位数字。假设前面取余后为m,则第二位数字是 第 m/(n-2)! 个未使用的数字。
4. 不断重复2,3,取余并且对(n-k)!进行除法,直至计算完毕

以下为主页君的代码,敬请指正:

解法1:

采用比较复杂的boolean来计算数字的索引(我们需要用一个boolean的数组来记录未使用的数字):

 package Algorithms.permutation;

 /*
The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3): "123"
"132"
"213"
"231"
"312"
"321" Given n and k, return the kth permutation sequence. Note: Given n will be between 1 and 9 inclusive.
* */
public class PermutationSequence {
public static String getPermutation(int n, int k) {
if (n == ) {
return "";
} // 先计算出(n)!
int num = ;
for (int i = ; i <= n; i++) {
num *= i;
} boolean[] use = new boolean[n];
for (int i = ; i < n; i++) {
use[i] = false;
} // 因为index是从0开始计算
k--;
StringBuilder sb = new StringBuilder();
for (int i = ; i < n; i++) {
// 计算完第一个数字前,num要除以(n)
num = num / (n - i); int index = k / num;
k = k % num; for (int j = ; j < n; j++) {
if (!use[j]) {
if (index == ) {
// 记录下本次的结果.
sb.append((j + ) + "");
use[j] = true;
break;
} // 遇到未使用过的数字,记录index
index--;
}
}
} return sb.toString();
} public static void main(String[] args) {
System.out.println(getPermutation(, ));
} }

解法2:

优化后,使用链表来记录未使用的数字,每用掉一个,将它从链表中移除即可。

 public String getPermutation1(int n, int k) {
// 1:17 -> 1:43
LinkedList<Character> digits = new LinkedList<Character>(); // bug 2: should only add n elements.
for (char i = ''; i <= '' + n; i++) {
digits.add(i);
} k = k - ;
StringBuilder sb = new StringBuilder(); int sum = ;
// n!
for (int i = ; i <= n; i++) {
sum *= i;
} int cur = n;
while (!digits.isEmpty()) {
sum /= cur;
cur--; int digitIndex = k / sum;
k = k % sum;
//Line 25: error: cannot find symbol: method digits(int)
sb.append(digits.get(digitIndex));
// remove the used digit.
digits.remove(digitIndex);
} return sb.toString();
}

解法3:

在2解基础进一步优化,使用for 循环替代while 循环,更简洁:

 public String getPermutation(int n, int k) {
// 1:17 -> 1:43
LinkedList<Character> digits = new LinkedList<Character>(); // bug 2: should only add n elements.
for (char i = ''; i <= '' + n; i++) {
digits.add(i);
} // The index start from 0;
k--;
StringBuilder sb = new StringBuilder(); int sum = ;
// n!
for (int i = ; i <= n; i++) {
sum *= i;
} for (int i = n; i >= ; i--) {
sum /= i;
int digitIndex = k / sum;
k = k % sum; //Line 25: error: cannot find symbol: method digits(int)
sb.append(digits.get(digitIndex)); // remove the used digit.
digits.remove(digitIndex);
} return sb.toString();
}

GitHub代码链接