Keshawn_lu's Blog

Leetcode 406. 根据身高重建队列

字数统计: 571阅读时长: 2 min
2020/11/20 Share

题目简介:

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对 (h, k) 表示,其中 h 是这个人的身高,k 是应该排在这个人前面且身高大于或等于 h 的人数。 例如:[5,2] 表示前面应该有 2 个身高大于等于 5 的人,而 [5,0] 表示前面不应该存在身高大于等于 5 的人。

编写一个算法,根据每个人的身高 h 重建这个队列,使之满足每个整数对 (h, k) 中对人数 k 的要求。

示例:

1
2
输入:[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

提示:

  • 总人数少于 1100 人。

思路:

首先以身高升序为第一主关键字,k降序为第二主关键字对数组进行排序。

由于是身高升序,所以在从前往后遍历时,插入元素时,答案数组中已排好的人的身高都不比当前的人高;又因为是根据k降序排序的,所以之前已经排好的拥有相同身高的人也不会影响当前的人所要插入的位置(因为h一样时,k小的人肯定是排在前面的)。

综上,在从前往后遍历时,之前的人不会影响当前的人根据k值来进行插入位置

所以在遍历时,每次根据身高大于或等于该人的人数(即k值),在答案数组中找到该人的正确位置(遇到有人的位置就跳过不计)。

最后返回答案数组即可

tip:

  • 学会使用vectorempty()函数。

代码如下:

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
class Solution {
public:

static bool cmp(vector<int>& p1, vector<int>& p2){

if(p1[0] != p2[0])
return p1[0] < p2[0];
else
return p1[1] > p2[1];
}

vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {

vector<vector<int>> res(people.size());

sort(people.begin(), people.end(), cmp);

for(int i = 0; i < people.size(); i++){

int pos = people[i][1] + 1;

for(int j = 0; j < res.size(); j++){

if(res[j].empty())
pos--; //有空位给 比people[i]高的人

if(!pos){

res[j] = people[i]; //找到位置了
break;
}
}
}

return res;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: