这道题主要涉及的是找规律和快速排序，优化时需要考虑 Java 中数据结构的特性。
原题
假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
注意：
总人数少于1100人。
示例1
2
3
4
5输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
原题url：https://leetcode-cn.com/problems/queue-reconstruction-by-height/
解题
两次快速排序
拿到这道题目，先想想规律。关注的重点应该在于这句话：k是排在这个人前面且身高大于或等于h的人数。
所以一般肯定是 h 大的在前面，但也需要考虑 k，当 h 相同时，肯定是 k 越小，越在前面。
这样也就涉及到了排序，排序中时间复杂度低的也就是快速排序和归并排序。本题并不需要考虑稳定性，因为原始的数组并没有规律，且并没有涉及原始数组的顺序，所以两种排序用哪个都可以。但考虑到快速排序写起来更简单，因此就采用它。
我的思路是：
- 先针对 h ，如果 h 越大，则越靠前(也就是降序)，做一次快速排序。
- 如果 h 相同时，再针对 k，如果 k 越小，则越靠前(也就是升序)，再做一次快速排序。
- 利用自定义的 TreeNode 结构，也就是单向链表，根据 k 进行插入。
- 遍历单向链表，输出最终结果
接下来看看代码：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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140class Solution {
public int[][] reconstructQueue(int[][] people) {
if (people.length <= 1) {
return people;
}
// 利用快排，针对people进行排序
// h越大，越靠前，降序
binarySort(people, 0, people.length - 1);
// h相等时，k越小越靠前，升序
sortByK(people);
// 构造树
TreeNode root = new TreeNode();
TreeNode temp = new TreeNode();
temp.val = people[0];
root.next = temp;
for (int i = 1; i < people.length; i++) {
int[] person = people[i];
// 根据k，往树中放
TreeNode preNode = root;
for (int j = 0; j < person[1]; j++) {
preNode = preNode.next;
}
// 添加节点
temp = new TreeNode();
temp.val = person;
temp.next = preNode.next;
preNode.next = temp;
}
// 最终结果
int[][] result = new int[people.length][2];
int index = 0;
root = root.next;
// 遍历并赋值
while (root != null) {
TreeNode node = root;
result[index] = node.val;
root = root.next;
index++;
}
return result;
}
public void sortByK(int[][] people) {
int start = 0;
int end = 1;
int[] prePeople = people[0];
// 遍历，找出相等的结果
while (end < people.length) {
// 如果两者不等
if (prePeople[0] != people[end][0]) {
if (end - start >= 2) {
binarySortByK(people, start, end - 1);
}
prePeople = people[end];
start = end;
}
// 如果两者相等，则什么都不需要改变
end++;
}
if (end - start >= 2) {
binarySortByK(people, start, end - 1);
}
}
public void binarySortByK(
int[][] people,
int left,
int right) {
// 终止条件
if (left >= right) {
return;
}
// 标准值(待比较)
int[] standard = new int[2];
standard[0] = people[left][0];
standard[1] = people[left][1];
// 提前记录
int low = left;
int high = right;
while (left < right) {
// 先从right找起，因为left的值已经被重新存储，可以被替换
while (left < right && people[right][1] >= standard[1]) {
right--;
}
people[left] = people[right];
// 再替换right
while (left < right && people[left][1] < standard[1]) {
left++;
}
people[right] = people[left];
}
// 最终left和right必然相等
people[right] = standard;
// 继续
binarySortByK(people, low, right - 1);
binarySortByK(people, right + 1, high);
}
public void binarySort(
int[][] people,
int left,
int right) {
// 终止条件
if (left >= right) {
return;
}
// 标准值(待比较)
int[] standard = new int[2];
standard[0] = people[left][0];
standard[1] = people[left][1];
// 提前记录
int low = left;
int high = right;
while (left < right) {
// 先从right找起，因为left的值已经被重新存储，可以被替换
while (left < right && people[right][0] < standard[0]) {
right--;
}
people[left] = people[right];
// 再替换right
while (left < right && people[left][0] >= standard[0]) {
left++;
}
people[right] = people[left];
}
// 最终left和right必然相等
people[right] = standard;
// 继续
binarySort(people, low, right - 1);
binarySort(people, right + 1, high);
}
}
class TreeNode {
int[] val;
TreeNode next;
}
提交OK，但执行时间较长，我们再优化优化。
优化
首先，针对快速排序，是否可以只用一次？答案是肯定的，我们只需要将比较条件特殊处理即可，也就是将上面两次的排序判断条件合并。
其次，针对最终结果的输出，我之前考虑用单向链表，是因为相比于数组每次插入时需要复制，链表的插入比较简单，只需要将地址换掉即可。但链表在找元素过程中耗时较长，数组可以直接利用下标计算出目标位置，且 Java 中的 ArrayList 的 add(int index, E element)，其复制方法是 native 类型，因此效率较高。所以我将最终的结果放入 ArrayList 进行处理。
接下来看看代码：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
72class Solution {
public int[][] reconstructQueue(int[][] people) {
if (people.length <= 1) {
return people;
}
// 利用快排，针对people进行排序
binarySort(people, 0, people.length - 1);
List<int[]> list = new ArrayList<>(people.length);
// 根据k向ArrayList中添加元素
for (int[] person : people) {
int k = person[1];
list.add(k, person);
}
// 转化为数组
return list.toArray(new int[people.length][2]);
}
public void binarySort(
int[][] people,
int left,
int right) {
// 终止条件
if (left >= right) {
return;
}
// 标准值(待比较)
int[] standard = new int[2];
standard[0] = people[left][0];
standard[1] = people[left][1];
// 提前记录
int low = left;
int high = right;
while (left < right) {
// 先从right找起，因为left的值已经被重新存储，可以被替换
while (left < right && !compare(people[right], standard)) {
right--;
}
people[left] = people[right];
// 再替换right
while (left < right && compare(people[left], standard)) {
left++;
}
people[right] = people[left];
}
// 最终left和right必然相等
people[right] = standard;
// 继续
binarySort(people, low, right - 1);
binarySort(people, right + 1, high);
}
public boolean compare(int[] person1, int[] person2) {
// h越大，越靠前，降序
int height1 = person1[0];
int height2 = person2[0];
if (height1 > height2) {
return true;
}
if (height1 < height2) {
return false;
}
// 当h相等时，k越小越靠前，升序
int k1 = person1[1];
int k2 = person2[1];
return k1 < k2;
}
}
提交OK，这样速度提升了至少一倍。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要涉及的是找规律和快速排序，优化时需要考虑 Java 中数据结构的特性。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。
公众号：健程之道
