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

【贪心】LeetCode-406. 根据身高重建队列

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

提示:

1 <= people.length <= 2000
0 <= hi <= 10^6
0 <= ki < people.length
题目数据确保队列可以被重建
算法分析

解题思路

  • 先排序,h升序,k降序
  • 根据k值站位
class Solution {public int[][] reconstructQueue(int[][] people) {//h升序,k降序Arrays.sort(people, (o1,o2) -> o1[0] != o2[0] ? o2[0]- o1[0] : o1[1] - o2[1]);List<int[]> ans = new ArrayList<int[]>();for (int[] person : people) {ans.add(person[1], person);}return ans.toArray(new int[ans.size()][]);}
}

复杂性分析

时间复杂度:O(n2)
空间复杂度:O(logn)

相关文章:

【贪心】LeetCode-406. 根据身高重建队列

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

【C++11特性篇】C++11中新增的initializer_list——初始化的小利器

前言 大家好吖&#xff0c;欢迎来到 YY 滴C11系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过C的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; 目录 一.探究std::initializer_list是什么…...

springboot(ssm宠物美容机构CRM系统 宠物服务商城系统Java系统

springboot(ssm宠物美容机构CRM系统 客户关系管理系统Java系统 开发语言&#xff1a;Java 框架&#xff1a;ssm/springboot vue JDK版本&#xff1a;JDK1.8&#xff08;或11&#xff09; 服务器&#xff1a;tomcat 数据库&#xff1a;mysql 5.7&#xff08;或8.0&#xff…...

LSTM 双向 Bi-LSTM

目录 一.Bi-LSTM介绍 二.Bi-LSTM结构 Bi-LSTM 代码实例 一.Bi-LSTM介绍 由于LSTM只能从序列里由前往后预测,为了既能够从前往后预测,也能从后往前预测,Bi-LSTM便被发明了出来。简单来说,BiLSTM就是由前向LSTM与后向LSTM组合而成。 二.Bi-LSTM结构 转自:...

2024测试开发面试题完整版本(附答案)

目录 1. 什么是软件测试&#xff0c; 谈谈你对软件测试的了解 2. 我看你简历上有写了解常见的开发模型和测试模型, 那你跟我讲一下敏捷模型 3. 我看你简历上还写了挺多开发技能的, 那你给我讲讲哈希表的实现流程 4. 谈一谈什么是线程安全问题, 如何解决 5. 既然你选择走测…...

MySQL作为服务端的配置过程与实际案例

MySQL是一款流行的关系型数据库管理系统&#xff0c;广泛应用于各种业务场景中。作为服务端&#xff0c;MySQL的配置过程对于数据库的性能、安全性和稳定性至关重要。本文将详细介绍MySQL作为服务端的配置过程&#xff0c;并通过一个实际案例进行举例说明。 一、MySQL服务端配…...

Appium 自动化自学篇 —— 初识Appium自动化!

Appium 简介 随着移动终端的普及&#xff0c;手机应用越来越多&#xff0c;也越来越重要。而作为测试 的我们也要与时俱进&#xff0c;努力学习手机 App 的相关测试&#xff0c;文章将介绍手机自动化测试框架 Appium 。 那究竟什么是 Appium 呢? 接下来我们一起来学习PythonS…...

Linux基本操作指令

哈喽小伙伴们&#xff0c;从这篇文章开始&#xff0c;在学习数据结构的同时&#xff0c;我们开启一个新的篇章——Linux操作系统的学习&#xff0c;这将会是又一个新的开始&#xff0c;希望小伙伴们能够认真细心&#xff0c;不要掉队哦。 目录 一.什么是Linux 二.为什么要学习…...

探索SD-WAN技术对传统制造业实现智能制造的作用

在智能制造背景下&#xff0c;传统制造业面临着日益增长的信息化建设需求。随着企业趋向数字化转型&#xff0c;构建稳定、高效的网络基础设施成为提升企业核心竞争力的重要一环。 制造业企业信息化建设中的组网需求&#xff1a; 第一&#xff0c;连接多地分支机构&#xff0c…...

C++基础-this指针详解

本文详细讲解C++this指针 定义 this 是 C++ 中的一个关键字,一个特殊的指针,它指向当前对象地址(换句话说,其值为 &object),通过它可以访问当前对象的所有成员。 类定义好后我们就可以通过类来创建多个实例对象,每个对象都有各自的实例属性(实例变量),但是非内…...

如何一键生成多个文件二维码?批量文件二维码制作技巧

文件能批量生成二维码吗&#xff1f;现在的二维码用途范围越来越广&#xff0c;比如常见的有图文、文件、问卷、音频或者视频等内容生成二维码图片&#xff0c;扫码查看内容。那么当需要将很多的文件每个都单独生成一个二维码时&#xff0c;有没有比较简单快捷的操作方法吗&…...

SQL连续

SQL连续 1、连续概述2、SQL连续及应用2.1、静态连续2.2、动态连续1、连续概述 连续问题是实际数据开发中比较常见的场景。例如,统计用户连续活跃天数等 SQL如何解决连续问题?本文主要介绍连续性问题,重点以常见的连续活跃场景为例,抽象出通用的连续问题解决方案。连续问题…...

sql server导出与导入

解决&#xff1a;不同版本sql server复制表、导数据&#xff1b;把数据库的结构和全部数据从2016版导入到2014版。 分离数据为mdf,ldf后&#xff0c;导入过程中无权限、被占用问题。 文章目录 使用脚本&#xff08;.sql文件&#xff09;导出导入备注 使用mdf&#xff0c;mlf导…...

DevEco Studio 项目鸿蒙(HarmonyOS)资源引用(自定统和系统)

DevEco Studio 项目鸿蒙&#xff08;HarmonyOS&#xff09;资源引用&#xff08;自定统和系统&#xff09; 一、操作环境 操作系统: Windows 10 专业版 IDE:DevEco Studio 3.1 SDK:HarmonyOS 3.1 二、资源访问 HarmonyOS应用资源分为两类&#xff0c;一类是应用资源&…...

使用国内镜像源安装opencv

在控制台输入命令&#xff1a; pip install opencv-python -i https://pypi.tuna.tsinghua.edu.cn/simple 验证安装&#xff1a; step 1&#xff1a; 打开终端&#xff1b;step 2&#xff1a; 输入python&#xff0c;进入Python编译环境&#xff1b;step 3&#xff1a; 粘贴…...

人工智能与大数据的紧密联系

随着科技的飞速发展&#xff0c;人工智能&#xff08;Artificial Intelligence&#xff0c;AI&#xff09;和大数据&#xff08;Big Data&#xff09;已成为当今社会的热门话题。人工智能在许多领域的应用越来越广泛&#xff0c;而大数据则提供了支持和驱动AI技术的巨大资源。本…...

macbookpro 2024怎么恢复出厂设置

可能你的MacBook曾经是高性能的代表&#xff0c;但是现在它正慢慢地逝去了自己的光芒&#xff1f;随着逐年的使用以及文件的添加和程序的安装&#xff0c;你的MacBook可能会开始变得迟缓卡顿&#xff0c;或者失却了以往的光彩。如果你发现你的Mac开始出现这些严重问题&#xff…...

Linux系统编程(二):标准 I/O 库(下)

参考引用 UNIX 环境高级编程 (第3版)嵌入式Linux C应用编程-正点原子 1. 标准 I/O 库简介 标准 I/O 库是指&#xff1a;标准 C 库中用于文件 I/O 操作&#xff08;如&#xff1a;读、写文件等&#xff09;相关的一系列库函数的集合 标准 I/O 库函数相关的函数定义都在头文件 &…...

Mr. Cappuccino的第65杯咖啡——MacOS安装Docker

MacOS安装Docker 下载Docker安装Docker查看Docker相关信息镜像加速 下载Docker Docker官网 Docker文档中心 Docker桌面版下载地址 安装Docker 查看Docker相关信息 docker --versiondocker info镜像加速 阿里云镜像加速器 "registry-mirrors": ["https://gq8…...

解决 Docker Hub 国内无法访问的方法(Docker 镜像下载加速)

参考文章&#xff1a; 知乎&#xff1a;解决目前Docker Hub国内无法访问方法汇总 docker配置 修改配置文件 vim /etc/docker/daemon.json配置内容如下&#xff1a; {"builder": {"gc": {"defaultKeepStorage": "20GB","enab…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...