当前位置:网站首页>leetcode 406. Queue Reconstruction by Height
leetcode 406. Queue Reconstruction by Height
2022-07-31 07:09:00 【okokabcd】
一、题目大意
标签: 贪心
https://leetcode.cn/problems/queue-reconstruction-by-height
假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序).每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ,前面 正好 有 ki 个身高大于或等于 hi 的人.
请你重新构造并返回输入数组 people 所表示的队列.返回的队列应该格式化为数组 queue ,其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性(queue[0] 是排在队列前面的人).
示例 1:
输入:people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释:
编号为 0 的人身高为 5 ,没有身高更高或者相同的人排在他前面.
编号为 1 的人身高为 7 ,没有身高更高或者相同的人排在他前面.
编号为 2 的人身高为 5 ,有 2 个身高更高或者相同的人排在他前面,即编号为 0 和 1 的人.
编号为 3 的人身高为 6 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人.
编号为 4 的人身高为 4 ,有 4 个身高更高或者相同的人排在他前面,即编号为 0、1、2、3 的人.
编号为 5 的人身高为 7 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人.
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列.
示例 2:
输入:people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出:[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
提示:
- 1 <= people.length <= 2000
- 0 <= hi <= 106
- 0 <= ki < people.length
- 题目数据确保队列可以被重建
二、解题思路
This question needs to be understood first,一个无序数组,数组中每个元素有两个属性,一个表示身高,One indicates that there are several people in front of him that are as tall or higher than him.Now let's sort this array correctly by its properties.
思路:~~创建一个list,Traverse the array sorted by height,Insert the second property as a positionlist中.~~将people数组排序,再通过一个变量cnt与krelationship to move the element forward to the correct position,The way to move is by swapping positions with the previous element each time.
三、解题方法
3.1 Java实现
public class Solution {
public int[][] reconstructQueue(int[][] people) {
// 先对peopleSort by height
Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
for (int i = 1; i < people.length; i++) {
int cnt = 0;
for (int j = 0; j < i; j++) {
if (cnt == people[i][1]) {
int[] t = people[i];
for (int k = i - 1; k >= j; k--) {
people[k+1] = people[k];
}
people[j] = t;
break;
}
cnt++;
}
}
return people;
}
}
四、总结小记
- 2022/7/30 7penultimate day of the month,It has rained heavily for the past two days
边栏推荐
猜你喜欢
随机推荐
Install the gstreamer development dependency library to the project sysroot directory
tidyverse笔记——管道函数
Dart入门
Koa框架的基本使用
英语翻译软件-批量自动免费翻译软件支持三方接口翻译
浅析伪类和伪元素
外贸网站优化-外贸网站优化教程-外贸网站优化软件
LeetCode刷题——摆动序列#376#Medium
试题 历届真题 错误票据【第四届】【省赛】【B组】
Oracle 日期函数相关
Gradle remove dependency demo
Difficulty comparison between high concurrency and multithreading (easy to confuse)
浅析重复线性渐变repeating-linear-gradient如何使用
一文读懂 MongoDB 和 MySQL 的差异
常用命令讲解
【云原生】-Docker容器迁移Oracle到MySQL
DNS域名解析服务
DHCP原理与配置
Redux state management
cp 的用法