[leetcode] 406. Queue Reconstruction by Height

Description

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.

Note: The number of people is less than 1,100.

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]]

分析

题目的意思是：给你一个数组，然后重建这个数组，数组中的每一个子数组代表[高度，排在前面的人数]。根据高度降序排序，如果高度一样，根据人数升序排序。 解法如下例子： [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

排序后：

[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

交换顺序：

[[7,0], [6,1], [7,1], [5,0], [5,2], [4,4]]

[[5,0], [7,0], [6,1], [7,1], [5,2], [4,4]]

[[5,0], [7,0], [5,2], [6,1], [7,1], [4,4]]

[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]] 先根据first降序排序，然后再根据second升序排列；然后把每个元素插入到resultvector操作，注意插入的操作。

代码

class Solution {public: vector> reconstructQueue(vector>& people) { auto comp=[](const pair&p1,const pair& p2){ return p1.first>p2.first||(p1.first==p2.first&&p1.second> result; for(auto &p:people){ result.insert(result.begin()+p.second,p); } return result; }};

参考文献

​​406. Queue Reconstruction by Height​​​​[LeetCode] Queue Reconstruction by Height 根据高度重建队列​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。