当前位置: 首页 > news >正文

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列,数组 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]]
 

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/queue-reconstruction-by-height
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路:

题目给了若干个数组,数组的第一个参数是第i个人的身高,第二个参数是第i个人前面有几个比自己高的人,根据题目要求,可以想到按照每个人的身高从高到低排序,再依次遍历每个人的第二个参数k,之所以先根据人的身高从低到高排序是为了遍历到某人的k值时直接将其移到第k个位置,因为身高是从高到低排的,所以移到数组下标为k的位置那么他前面就刚好有k个比他高的人,即使再向后。

那分析到这里可以意识到,一开始遗漏掉了题目里的另一个条件,题目给的k的含义是排在当前位置的人前面有k个大于或等于当前位置人的身高的数量,开始没注意到这个等于的条件导致一些用例测试错误。

输入:       [[9,0],[7,0],[1,9],[3,0],[2,7],[5,3],[6,0],[3,4],[6,2],[5,2]]

输出:       [[3,0],[6,0],[7,0],[5,2],[3,4],[6,2],[5,3],[2,7],[9,0],[1,9]]

预期结果:[[3,0],[6,0],[7,0],[5,2],[3,4],[5,3],[6,2],[2,7],[9,0],[1,9]]

 找到问题之后,将相同身高的人按照其k值的大小从低到高排序便解决了这个问题。

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0] > o2[0] ? -1 : (o1[0] == o2[0])&&(o1[1] < o2[1]) ? -1 : 1;}});int length = people.length;for (int i = 0; i < length; i++) {insertPeople(i, people[i][1], people);}return people;}public void insertPeople(int sour, int dest, int[][] people) {int sourH = people[sour][0];int sourK = people[sour][1];for (int i = sour; i > dest; --i) {people[i][0] = people[i - 1][0];people[i][1] = people[i - 1][1];}people[dest][0] = sourH;people[dest][1] = sourK;}
}

 另一种排序的方法

Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);

 

方法二:List进行插值

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, ((o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]));List<int[]> queue = new ArrayList<int[]>();int length = people.length;for(int[] p:people){queue.add(p[1],p);//根据k把p插到对应的序号}return queue.toArray(new int[people.length][2]);}
}

优化排序

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0] > o2[0] ? -1 : (o1[0] == o2[0]) && (o1[1] < o2[1]) ? -1 : 1;}});List<int[]> queue = new ArrayList<int[]>();int length = people.length;for(int[] p:people){queue.add(p[1],p);//根据k把p插到对应的序号}return queue.toArray(new int[people.length][2]);}
}

 

相关文章:

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列&#xff0c;数组 people 表示队列中一些人的属性&#xff08;不一定按顺序&#xff09;。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi &#xff0c;前面 正好 有 ki 个身高大于或等于 hi 的人。 请你重新构造并返回输入数组 peopl…...

ESP32使用ESP-NOW协议实现一对多通信和MAC地址存储

目录 介绍ESP-NOW 协议概述在 ESP32 上配置 ESP-NOW使用 ESP-NOW 进行一对多通信在 ESP32 上存储发件人的 MAC 地址代码结论 介绍 ESP32 是一款功能强大的 Wi-Fi 和蓝牙双模模块&#xff0c;可用于使用 ESP-NOW 协议实现低功耗、高效率的一对多通信。本文将介绍如何使用ESP-NO…...

Qt 学生信息数据库管理

1 添加样式表 我们采用了样式表 通过添加Qt resources文件 添加前缀 添加文件&#xff0c;将我们的图标进行添加 2 拖动部件 用到的部件 Label 标签Pushbutton 按钮table view 视图LineEdit 输入框 3 程序编写 1 配置sql环境 在 pro文件中 添加 连接数据库跟访问数据…...

相量的加减乘除计算

相量的加减乘除计算 矢量是物理学中的术语&#xff0c;是指具有大小&#xff08;magnitude&#xff09;和方向的量。如速度、加速度、力等等就是这样的量。向量是数学中的术语&#xff0c;也称为欧几里得向量、几何向量、矢量。与向量对应的量叫做数量&#xff0c;在物理学中称…...

JavaScript 代码整洁之道

文章目录 概述篇变量篇函数篇注释篇异常处理篇复杂判断函数篇重构篇代码风格常量大写先声明后调用注释 参考资料 概述篇 书写能让人读懂的代码使用英语编写代码团队协作 制定通用的规则&#xff0c;依靠工具让团队的代码风格保持统一&#xff0c;要让代码看起来是由一个人编写…...

socket 及 字节序转换(嵌入式学习)

socket 及 字节序转换 socket简介Socket为什么需要Socket&#xff1f;socket类型Socket通信模型 字节序主机字节序到网络字节序网络字节序到主机字节序IP地址转换 socket简介 1、1982 - Berkeley Software Distributions 操作系统引入了socket作为本地进程之间通信的接口 2、1…...

Java之~ Aop自定义注解日志

大纲步骤&#xff1a; 一&#xff0c;创建需要记录的日志表&#xff0c;创建基础方法。&#xff08;省略&#xff09; 二&#xff0c;在需要加记录日志的方法上加Aop注解1&#xff0c;创建一个注解类&#xff0c;Aop中定义一个注解import java.lang.annotation.*; /*** http 请…...

编译原理个人作业--第四章

构造FIRST和FOLLOW的大白话网站 第四章 1 考虑文法 G 1 G_1 G1​: S → a ∣ ∧ ∣ ( T ) T → T , S ∣ S S \rightarrow a|\land|(T) \\ T\rightarrow T,S|S S→a∣∧∣(T)T→T,S∣S 先复习左递归如何消除 原书p69页 类似于 P → P a ∣ b P\rightarrow Pa|b P→Pa∣b的…...

学习笔记:数据库简介

数据库是一系列可以方便的访问和修改的数据的集合。 所有数据库管理系统的主要工作都是可靠的存储数据并使其对用户可用。 目前最常见的数据库模型主要是两种&#xff0c;即关系型数据库和非关系型数据库。 一、按数据的组织方式 数据从组织的角度上&#xff0c;主要分为结…...

day18_集合

今日内容 零、 复习昨日 一、集合框架体系 二、Collection 三、泛型 四、迭代 五、List 六、ArrayList 七、LinkedList 零、 复习昨日 晨考 一、集合框架体系 数组: 是一个容器,用来存放数据的 定长只能存储同一种数据类型的数据int[] 可以存储int值,Student[] 可以存储引用类型…...

Go面试必会基础题

文章目录 1.下面代码有什么错误&#xff1f;2.下面代码有什么问题&#xff1f;3.下面代码输出什么&#xff1f;4.下面这段代码输出什么&#xff1f; 1.下面代码有什么错误&#xff1f; func main() {one : 0one : 1 }参考答案及解析&#xff1a;变量重复声明。不能在单独的声…...

发送封包协议实现XXZ批量秒分解装备

通过发送封包&#xff0c;我们可以让一些反复的枯燥的行为变的简单&#xff0c;高效。 比如XXZ的萃取装备&#xff0c;我们可以一瞬间萃取大量的装备&#xff0c;而省去读条的过程。 我们来萃取一下看看效果 手动萃取是有读条的&#xff0c;那么如果很多装备的话&#xff0c;…...

Spring学习——Nginx

Nginx概述 Nginx介绍 Nginx是一款轻量级的web 服务器/反向代理服务器及电子邮件&#xff08;IMAP/POP3&#xff09;代理服务器。其特点是占有内存少&#xff0c;并发能力强&#xff0c;事实上nginx的并发能力在同类型的网页服务器中表现较好&#xff0c;中国大陆使用nginx的网…...

记录 vue-cli 安装过程

1. VueCli CLI 是 Commond-Line Interface 的缩写 如果开发大型项目&#xff0c;肯定需要考虑代码目录结构、项目结构和部署、热加载、代码单元测试等事情&#xff0c;那么你必然需要使用 VueCLI&#xff0c;使用 VueCLI 可以快速搭建 vue 开发环境以及对应的 webpack 配置。 …...

含氢微网优化调度模型matlab

目录 1 主要内容 模型示意图 目标函数 2 部分程序 3 程序结果 4 下载链接 1 主要内容 最近咨询含氢微网优化调度模型的同学较多&#xff0c;本次就分享一个高质量的源码资源。该程序方法复现《Simulation of design and operation of hydrogen energy utilization syste…...

【springcloud开发教程】路由网关——zuul

官方资料&#xff1a;https://github.com/Netflix/zuul/ 什么是Zuul? Zuul包含了两个主要的功能&#xff1a;路由和过滤 路由功能将外部请求转发到具体的微服务实例上&#xff0c;是实现外部访问统一入口的基础&#xff0c;而过滤器功能则负责对请求的处理过程进行干预&#…...

DF竞赛平台携手嬴彻科技与清华大学智能产业研究院,助力自动驾驶挑战赛圆满落幕!

由DataFountain竞赛平台&#xff08;简称DF平台&#xff09;提供办赛支持的「首届“嬴彻-清华AIR杯”自动驾驶挑战赛&#xff1a;决策规划算法」已圆满落幕。作为一场前沿性自动驾驶类比赛&#xff0c;本次大赛立足“高速道路”和“城市道路”两大真实场景&#xff0c;选择“半…...

234:vue+openlayers 加载本地shp数据,在map上显示图形

第234个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+openlayers中利用shapefile读取本地的shp数据,并在地图上显示图形。 直接复制下面的 vue+openlayers源代码,操作2分钟即可运行实现效果 文章目录 示例效果安装引用配置方式示例源代码(共143行)相关API参考:专栏…...

网络模型-网络体系结构(OSI、TCP/IP)

网络模型&#xff08;网络体系结构&#xff09; 网络模型网络的体系结构OSI模型TCP/IP模型OSI和TCP/IP模型对应关系图 常见网络协议 网络模型 网络的体系结构 1、网络采用分而治之的方法设计&#xff0c;将网络的功能划分为不同的模块&#xff0c;以分层的形式有机组合在一起…...

园区智慧导览地图软件,智慧工厂导航定位怎么解决方案的

智慧工厂导航定位怎么解决方案的地图新基建是行业的核心数字基础需求之一&#xff0c;行业内中已构建了较为完整的城市级地理信息系统。园区管理涉及众多方面&#xff0c;因此园区的智慧信息化建设至关重要&#xff0c;需求越来越广泛。在智慧园区中&#xff0c;基于园区的电子…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...