LC 406. Queue Reconstruction by Height
2024-08-30 08:04:07
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]]
Runtime: 32 ms, faster than 52.69% of C++ online submissions for Queue Reconstruction by Height.
按身高降序排列,身高相同的按第二个数升序排列。
然后我们一个一个按照第二个数的index插入一个新的序列。这样做的好处是,插入后面的数不会对之前的数产生
影响。
但这种做法需要新开一个数组,如果你不想新开一个数组,可以在当前数组种修改,但如果是vector其实提升效果一般吧,最好开一个链表。
#include <assert.h>
#include <map>
#include <iostream>
#include <vector>
#include <algorithm>
#define ALL(x) (x).begin(), (x).end()
using namespace std;
class Solution {
public:
static bool sortcmp(const pair<int,int> a, const pair<int,int> b){
if(a.first == b.first) return a.second < b.second;
return a.first > b.first;
}
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
vector<pair<int,int>> ret;
if(people.empty()) return ret;
sort(ALL(people), sortcmp);
for(int i=; i<people.size(); i++){
ret.insert(ret.begin() + people[i].second, people[i]);
}
return ret;
}
};
最新文章
- PYTHON 随机验证码生成
- [ASP.NET MVC 小牛之路]01 - 理解MVC模式
- Apkplug 开发常见问题解答
- NPOI操作Excel导入DataTable中
- struct 理解 (需要经常理解)
- [LeetCode] 187. Repeated DNA Sequences 解题思路
- .NET委托:一个关于C#的睡前故事 【转】
- PHP 字符串正则替换函数preg_replace使用说明
- rpm安装查看卸载软件
- 如何用chrome扩展将网页变成黑底白字,用以保护视力
- MySQL慢查询日志总结 日志分析工具mysqldumpslow
- poj2299树状数组入门,求逆序对
- rest-framework 序列化格式Restful API设计规范
- Python Scrapy环境搭建(一)
- 【ZZ】技能表合集
- PS添加透明立体水印
- 写一写关于python开发面试的常遇到的问题以及解答吧,持续更新——看心情
- [工具]Tomcat CVE-2017-12615 远程代码执行
- 浅谈iOS 自动调节文本高度
- java 结束程序进程 代码
热门文章
- ubuntu16.04 安装go
- ubuntu版本信息查看
- 【转】container_of宏 分析
- 十二,k8s集群访问控制之RBAC授权
- 通过WSL使用rsync同步本文件
- C语言-数字字符串转换成这个字符串对应的数字(十进制、十六进制)
- Kaggle_泰坦尼克乘客存活预测
- CF981F 二分+Hall定理
- CSS基础学习-4.CSS属性_背景、颜色、边框
- SpringMVC配置文件详解:<;context:annotation-config/>;和<;context:component-scan base-package=";";/>;和<;mvc:annotation-driven />;