LN : leetcode 406 Queue Reconstruction by Height
2024-09-30 00:57:01
lc 406 Queue Reconstruction by Height
406 Queue Reconstruction by Height
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]]
贪心算法 Accepted
首先,利用sort函数对people数组进行排序,使其中的顺序变为高度最高的在最前面,当高度一样时,令k值小的排在前面,优先满足最高且k最小的人的需求。
最后,依次将人插入到当前ans第k+1个的位置,得到的ans数组即为所求排序。
正确性解释:最高且k较小的人具有更高的优先性,因为当其已被插入,之后再插入的人,对在他之前比他高或相等的人的个数没有影响。
class Solution {
public:
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
auto cmp = [](pair<int, int>& p1, pair<int, int>& p2) {
return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second);
};
sort(people.begin(), people.end(), cmp);
vector<pair<int, int>> ans;
for (auto&p : people) ans.insert(ans.begin()+p.second, p);
return ans;
}
};
最新文章
- JAVA NIO学习笔记1 - 架构简介
- Visual studio 类视图和资源视图不显示的问题
- blcok的总结
- AC_Dream 1216 G - Beautiful People
- 常见的几种RuntimeException
- Linux下软件安装方法即路径设置
- Redis初步
- Swift中的注释以及表达式
- (poj 3177) Redundant Paths
- 自制的七个C,总结的太好了
- HDU4731+找规律
- OpenStack回顾随笔(第一章)
- Java利用自定义注解、反射实现简单BaseDao
- 汉诺塔python3函数编写和过程分析
- J2EE学习从菜鸟变大鸟之四 JNDI(Java Naming and Directory Interface)
- openstack 5大组件之间的关系和基本架构思维导图
- 0109 ubuntu nginx ssl
- make menuconfig 笔记
- python调用数据返回字典dict数据的现象1
- Centos6下安装中文字体
热门文章
- 【Hibernate学习】 ——ORM(一)
- cout 堆栈,operator&;lt;&;lt; 运算符重载输出问题
- C# .Net 多进程同步 通信 共享内存 内存映射文件 Memory Mapped 转 VC中进程与进程之间共享内存 .net环境下跨进程、高频率读写数据 使用C#开发Android应用之WebApp 分布式事务之消息补偿解决方案
- .NET Core/.NET之Stream简介 Rx.NET 简介
- Struts2默认拦截器栈及内建拦截器使用具体解释
- GDI+学习之------ 画线、区域填充、写字
- C#下JSON字符串的反序列化
- PHP博客项目-gai
- rabbitmq最大连接数(Socket Descriptors)
- Docker Image发布