【贪心】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. 根据身高重建队列。 假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi ,前面 正好 有 ki 个身高大于或等于 hi 的人。 请你重新…...

【C++11特性篇】C++11中新增的initializer_list——初始化的小利器
前言 大家好吖,欢迎来到 YY 滴C11系列 ,热烈欢迎! 本章主要内容面向接触过C的老铁 主要内容含: 欢迎订阅 YY滴C专栏!更多干货持续更新!以下是传送门! 目录 一.探究std::initializer_list是什么…...
springboot(ssm宠物美容机构CRM系统 宠物服务商城系统Java系统
springboot(ssm宠物美容机构CRM系统 客户关系管理系统Java系统 开发语言:Java 框架:ssm/springboot vue JDK版本:JDK1.8(或11) 服务器:tomcat 数据库:mysql 5.7(或8.0ÿ…...
LSTM 双向 Bi-LSTM
目录 一.Bi-LSTM介绍 二.Bi-LSTM结构 Bi-LSTM 代码实例 一.Bi-LSTM介绍 由于LSTM只能从序列里由前往后预测,为了既能够从前往后预测,也能从后往前预测,Bi-LSTM便被发明了出来。简单来说,BiLSTM就是由前向LSTM与后向LSTM组合而成。 二.Bi-LSTM结构 转自:...

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

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

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

Linux基本操作指令
哈喽小伙伴们,从这篇文章开始,在学习数据结构的同时,我们开启一个新的篇章——Linux操作系统的学习,这将会是又一个新的开始,希望小伙伴们能够认真细心,不要掉队哦。 目录 一.什么是Linux 二.为什么要学习…...
探索SD-WAN技术对传统制造业实现智能制造的作用
在智能制造背景下,传统制造业面临着日益增长的信息化建设需求。随着企业趋向数字化转型,构建稳定、高效的网络基础设施成为提升企业核心竞争力的重要一环。 制造业企业信息化建设中的组网需求: 第一,连接多地分支机构,…...
C++基础-this指针详解
本文详细讲解C++this指针 定义 this 是 C++ 中的一个关键字,一个特殊的指针,它指向当前对象地址(换句话说,其值为 &object),通过它可以访问当前对象的所有成员。 类定义好后我们就可以通过类来创建多个实例对象,每个对象都有各自的实例属性(实例变量),但是非内…...

如何一键生成多个文件二维码?批量文件二维码制作技巧
文件能批量生成二维码吗?现在的二维码用途范围越来越广,比如常见的有图文、文件、问卷、音频或者视频等内容生成二维码图片,扫码查看内容。那么当需要将很多的文件每个都单独生成一个二维码时,有没有比较简单快捷的操作方法吗&…...
SQL连续
SQL连续 1、连续概述2、SQL连续及应用2.1、静态连续2.2、动态连续1、连续概述 连续问题是实际数据开发中比较常见的场景。例如,统计用户连续活跃天数等 SQL如何解决连续问题?本文主要介绍连续性问题,重点以常见的连续活跃场景为例,抽象出通用的连续问题解决方案。连续问题…...
sql server导出与导入
解决:不同版本sql server复制表、导数据;把数据库的结构和全部数据从2016版导入到2014版。 分离数据为mdf,ldf后,导入过程中无权限、被占用问题。 文章目录 使用脚本(.sql文件)导出导入备注 使用mdf,mlf导…...

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

使用国内镜像源安装opencv
在控制台输入命令: pip install opencv-python -i https://pypi.tuna.tsinghua.edu.cn/simple 验证安装: step 1: 打开终端;step 2: 输入python,进入Python编译环境;step 3: 粘贴…...

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

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

Linux系统编程(二):标准 I/O 库(下)
参考引用 UNIX 环境高级编程 (第3版)嵌入式Linux C应用编程-正点原子 1. 标准 I/O 库简介 标准 I/O 库是指:标准 C 库中用于文件 I/O 操作(如:读、写文件等)相关的一系列库函数的集合 标准 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 镜像下载加速)
参考文章: 知乎:解决目前Docker Hub国内无法访问方法汇总 docker配置 修改配置文件 vim /etc/docker/daemon.json配置内容如下: {"builder": {"gc": {"defaultKeepStorage": "20GB","enab…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...

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

阿里云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、运行以下命令卸载所有冲突的软件包: 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 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

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