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:

  • 学会使用vector的empty()函数。

代码如下：

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. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网