LeetCode 60. Permutation Sequence

题目链接 Permutation Sequence



这题是一道排列的题,题意是让你寻找1到 n 的数字的排列中第 k 个数(排列顺序按全排列从小到大来排)

这题我的思路是这样的

首先,我们知道1-9的阶乘结果,这个毫无疑问

其次,我们知道如,1,2,3 这3个数的全排列数量是6个,假设 n 为4,的情况我们首先可以确定第 k 个数的最高位是几,最高位可能是1,2,3,4

我们的排列是这样的

1 + {2,3,4的全排列}

2 + {1,3,4的全排列}

3 + {1,2,4的全排列}

4 + {2,3,4的全排列}

k为1-6的时候最高位为1

k 为7-12的时候最高位为2

以此类推

如果 k 都-1

那么

k 为0-5的时候最高位为1

k 为6-11的时候最高位为2

以此类推

这时k 有个特点

k / 6的值对于相同最高位的区间是一样的

这是我们可以想到我们维护一个列表,列表内容是1,2,3,4,5…n

此时 k/6的值就是最高位对应的一个下标,然后对剩下的第k % 6这个数再做排列

我自己一开始写的代码用的递归的方式,击败了44.44%,然后又用循环改写了一下,击败了71.49%.两种方式都是1A

循环方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static String getPermutation(int n, int k) {
int[] factorial = new int[10];
factorial[0] = 1;
for (int i = 1; i <= 9; i++) {
factorial[i] = factorial[i - 1] * i;
}
List<Integer> number = new ArrayList<>();
for (int i = 1; i <= 9; i++) {
number.add(i);
}
StringBuilder stringBuilder = new StringBuilder();
k--;
for (int i = 0; i < n; i++) {
int index = k / factorial[n - i - 1];
stringBuilder.append(number.get(index));
number.remove(index);
k = k - factorial[n - i - 1] * index;
}
return stringBuilder.toString();
}

递归方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
static int[] factorial = new int[10];

static int[] number = new int[11];
static int end = 9;
public static String getPermutation(int n, int k) {
end = n + 1;
factorial[1] = 1;
for (int i = 2; i <= 9; i++) {
factorial[i] = factorial[i - 1] * i;
}
for (int i = 1; i <= 9; i++) {
number[i] = i;
}
if (k % factorial[n] == 0) {
return remain();
}
return aha(n - 1, k);
}

public static void remove(int[] a, int index) {
a[end] = a[index];
for (int i = index + 1; i < end; i++) {
a[i - 1] = a[i];
}
end--;
}

public static String remain() {
StringBuilder stringBuilder = new StringBuilder();
for (int i = end - 1; i >= 1; i--) {
stringBuilder.append(number[i]);
}
return stringBuilder.toString();
}

public static String remain2() {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 1; i <= end - 1; i++) {
stringBuilder.append(number[i]);
}
return stringBuilder.toString();
}

public static String aha(int n, int k) {
if (n != 1 && k == 0) {
return remain2();
}
if (n == 0) {
return 1 + "";
}
if (n == 1) {
if (k == 1) {
return "" + number[1] + number[2];
} else {
return "" + number[2] + number[1];
}
}
if (k > factorial[n]) {
int inc = k / factorial[n];
int next = k % factorial[n];
if (next == 0) {
int temp = number[inc];
remove(number, inc);
return temp + remain();
}
int tempIndex = 1 + inc;
int temp = number[tempIndex];
remove(number, tempIndex);
return temp + aha(n - 1, next);
} else if (k < factorial[n]) {
int temp = number[1];
remove(number, 1);
return temp + aha(n - 1, k);
} else {
int temp = number[1];
remove(number, 1);
return temp + remain();
}
}
月月说要给我打赏,就还是放了二维码,😝