leetcode 406. Queue Reconstruction by Height

迈不过友情╰ 2022-06-13 00:22 91阅读 0赞

# 1.题目 #

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

若N个人排队，每个人用一个pair(h,k)表示，h–人的身高，k–此人前面有k个人的身高>=k  
这N的pair的顺序打乱了，要求重新构造原始的排队队列

Note:  
The number of people is less than 1,100. 队列长度<1100

Example

Input:打乱的队列  
\[\[7,0\], \[4,4\], \[7,1\], \[5,0\], \[6,1\], \[5,2\]\]

Output:还原的队列  
\[\[5,0\], \[7,0\], \[5,2\], \[6,1\], \[4,4\], \[7,1\]\]

# 2.分析 #

如何还原队列，即求出每个人的位置。pair

# 3.代码 #

class Solution {
    public:
        static bool mycmp(pair<int, int> a, pair<int, int> b) {
            if (a.first != b.first)
                return a.first > b.first;
            else
                return a.second < b.second;
        }
        vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
            vector<pair<int, int>> res;
            std::sort(people.begin(), people.end(), mycmp);//原始队列排序
            for (auto p:people)
                res.insert(res.begin() + p.second, p);//插入到结果队列
            return res;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，91人围观）

还没有评论，来说两句吧...

相关阅读

相关 Queue Reconstruction by Height（C++根据身高重建队列）

解题思路：（1）先排序，将空位留给比当前人的身高高的人参考网址：https://leetcode.com/problems/queue-reconstruction-

雨点打透心脏的1/2处/ 2023年01月06日 01:13/ 0 赞/ 137 阅读

相关 leetcode 406. Queue Reconstruction by Height | 406. 根据身高重建队列（Java）

题目 [https://leetcode.com/problems/queue-reconstruction-by-height/][https_leetcode.com

╰半橙微兮°/ 2022年08月29日 10:15/ 0 赞/ 105 阅读

相关 406. Queue Reconstruction by Height（根据身高重排队列）

Suppose you have a random list of people standing in a queue. Each person is described b

Myth丶恋晨/ 2022年07月15日 08:07/ 0 赞/ 121 阅读

相关【leetcode】406. Queue Reconstruction by Height

406. Queue Reconstruction by Height 题目 Suppose you have a random list of people st

妖狐艹你老母/ 2022年07月03日 20:22/ 0 赞/ 91 阅读

相关 [leetcode] 406. Queue Reconstruction by Height -- JavaScript 代码

先上代码： var reconstructQueue = function(people) { //var length = people.leng

小灰灰/ 2022年06月18日 06:54/ 0 赞/ 121 阅读

相关 leetcode 406. Queue Reconstruction by Height

1.题目 Suppose you have a random list of people standing in a queue. Each person is des

迈不过友情╰/ 2022年06月13日 00:22/ 0 赞/ 92 阅读

相关 leetcode 406. Queue Reconstruction by Height 人群高度排序

Suppose you have a random list of people standing in a queue. Each person is described b

港控/mmm°/ 2022年06月03日 19:59/ 0 赞/ 84 阅读

相关 LeetCode:406. Queue Reconstruction by Height(对人进行排序)

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

深藏阁楼爱情的钟/ 2022年04月08日 10:44/ 0 赞/ 135 阅读

相关【LeetCode Top 100】406. Queue Reconstruction by Height【Medium】【JAVA】

1. 题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9n

ゝ一世哀愁。/ 2021年09月21日 04:58/ 0 赞/ 185 阅读

相关 LeetCode : 406. Queue Reconstruction by Height 重构身高，序号队列

试题 Suppose you have a random list of people standing in a queue. Each person is descri

亦凉/ 2021年06月24日 16:10/ 0 赞/ 251 阅读