1. question: 根据身高重建队列（中等）
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/queue-reconstruction-by-height
示例 1：
1
2
3
4
5
6
7
8
9
10
| 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
|
示例 2：
1
2
| 输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
|
提示：
1
2
3
4
| 1 <= people.length <= 2000
0 <= hi <= 106
0 <= ki < people.length
题目数据确保队列可以被重建
|
2. answers
这道题不仔细分析还是比较容易模糊的。
这道题需要仔细阅读。将给定的数组重新排列，使其满足如下要求：
- 数组中每个元素表示一个人。
- 元素是二元组，第一个元素是身高，第二个元素是前面大于等于本人身高的人的个数。
给定的数组是打乱顺序的，因此本题就是还原为真正的数组，满足上面的要求。
首先不能简单地根据身高来排列，因为元组中的第二个元素可能不满足要求人数。也不能根据元组中的第二个元素来排列，因为身高可能也不满足要求。
仔细分析，可发现如下：
- 身高最高的人，所以该元组的第二个元素一定是0，无论其排放在哪个位置，都是满足要求的。
- 身高次高的人，第二个元素不一定是1，可以是[0, 1]，如果是0，只需要其放在身高最高的人前面即可。
- 身高第三高的人，第二个元素的取值可以是[0, 1, 2]，如果是0，只需要放在前两个高的人的前面即可。如果是1，则需放在第二个高的前面。
- …以此类推。
注意，上面第二个元素取值一定不会超过其范围，因为超过了之后，根本就没有比他大的更多人，肯定无法满足要求的。
所以说，在对身高矮的人排队时，一定是要知道身高高的人的顺序的。【更准确一点地说，身高矮的是依据第二个元素插入到已知的队列中的】
进一步说，身高高的人是很容易满足要求的。身高矮的人，则是依据第二个元素插入到队列中。（因为它们不会比身高高的人高，也就不会影响它们是否满足第二个元素）。所以，先按照身高对人进行降序排列。【对于身高相同的人，按照第二个元素进行升序排列，这样正好满足了第二个元素要求】。之后，从第二人开始，根据第二个元素的值，遍历前面的队列（是几，就插入到第几个元素的前面），插入到队列中。因为涉及到频繁的插入操作，似乎采用链表更加合适。
不难发现，其实本题的思路也是从两个维度来考虑的，首先根据身高进行排序。然后根据人数在上个排序的基础上再次排序。和分发糖果有点类似。
代码如下所示：
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
| public class Solution_0103 {
public List<int[]> sortQueue(int[][] people) {
int[] person;
List<int[]> list = new LinkedList<>();
for (int i = 0; i < people.length - 1; i++) {
for (int j = i + 1; j < people.length; j++) {
if(people[j][0] > people[i][0]) {
person = people[i];
people[i] = people[j];
people[j] = person;
}
else if(people[j][0] == people[i][0] && people[j][1] < people[i][1]) {
person = people[i];
people[i] = people[j];
people[j] = person;
}
}
int[] temp = {people[i][0], people[i][1]};
list.add(temp);
}
int[] fin = {people[people.length - 1][0], people[people.length - 1][1]};
list.add(fin);
return list;
}
public int[][] reconstructQueue(int[][] people) {
List<int[]> list = sortQueue(people);
for (int i = 1; i < list.size(); i++) {
int[] map = list.get(i);
int pre = map[1];
if(pre < i) {
for (int j = 0; j < i; j++) {
if(pre == 0) {
list.remove(i);
list.add(j, map);
break;
}
int[] temp = list.get(j);
if(temp[0] > map[0] || (temp[0] == map[0] && temp[1] < map[1])) pre--;
}
}
}
int index = 0;
int[][] result = new int[people.length][2];
for(int[] map: list) {
result[index][0] = map[0];
result[index][1] = map[1];
index++;
}
return result;
}
public static void main(String[] args) {
System.out.println();
int[][] people = {{6,0},{5,0},{4,0},{3,2},{2,2},{1,4}};
Solution_0103 s = new Solution_0103();
int[][] result = s.reconstructQueue(people);
for(int[] i: result)
System.out.print("[" + i[0] + "," + i[1] + "]" + "\t");
}
}
|
上面是自己想出来的代码。参考题解，其实也是这种思路，只不过代码更加简洁，如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a, b) -> {
if (a[0] == b[0]) return a[1] - b[1];
return b[0] - a[0];
});
LinkedList<int[]> que = new LinkedList<>();
for (int[] p : people) {
que.add(p[1],p);
}
return que.toArray(new int[people.length][]);
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
