【Leetcode 每日一题】2545. 根据第 K 场考试的分数排序
问题背景
班里有 m m m 位学生,共计划组织 n n n 场考试。给你一个下标从 0 0 0 开始、大小为 m × n m \times n m×n 的整数矩阵 s c o r e score score,其中每一行对应一位学生,而 s c o r e [ i ] [ j ] score[i][j] score[i][j] 表示第 i i i 位学生在第 j j j 场考试取得的分数。矩阵 s c o r e score score 包含的整数 互不相同 。
另给你一个整数 k k k。请你按第 k k k 场考试分数从高到低完成对这些学生(矩阵中的行)的排序。
返回排序后的矩阵。
数据约束
- m = s c o r e . l e n g t h m = score.length m=score.length
- n = s c o r e [ i ] . l e n g t h n = score[i].length n=score[i].length
- 1 ≤ m , n ≤ 250 1 \le m, n \le 250 1≤m,n≤250
- 1 ≤ s c o r e [ i ] [ j ] ≤ 105 1 \le score[i][j] \le 105 1≤score[i][j]≤105
- s c o r e score score 由 不同 的整数组成
- 0 ≤ k < n 0 \le k \lt n 0≤k<n
解题过程
根据某个标准带着整个数组排序,可以当作模板记下来。
题目保证待排序的元素不重复,那就可以完全不考虑稳定性的问题。
写一下在其它算法中常用 O ( N l o g N ) O(NlogN) O(NlogN) 量级的简单做法,再把三种常用排序都实现一下当作练习好了。
具体实现
调用 API
class Solution {public int[][] sortTheStudents(int[][] score, int k) {Arrays.sort(score, (o1, o2) -> o2[k] - o1[k]);return score;}
}
归并排序 - 递归版
class Solution {// 二维数组最大长度为 250,开长为 300 的辅助数组就够了private static final int MAX_N = 300;private static final int[][] temp = new int[MAX_N][];private int k;public int[][] sortTheStudents(int[][] score, int k) {this.k = k;mergeSort(score, 0, score.length - 1);return score;}// 归并操作,入参改成二维数组private void merge(int[][] arr, int left, int mid, int right) {int index1 = left, index2 = mid + 1, index = left;while(index1 <= mid && index2 <= right) {// 除了收集元素的标准不一样,其它都可以不变temp[index++] = arr[index1][k] > arr[index2][k] ? arr[index1++] : arr[index2++];}while(index1 <= mid) {temp[index++] = arr[index1++];}while(index2 <= right) {temp[index++] = arr[index2++];}System.arraycopy(temp, left, arr, left, right - left + 1);}// 归并排序,入参改成二维数组private void mergeSort(int[][] arr, int left, int right) {if(left == right) {return;}int mid = left + ((right - left) >>> 1);mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}
}
归并排序 - 非递归版
class Solution {// 二维数组最大长度为 250,开长为 300 的辅助数组就够了private static final int MAX_N = 300;private static final int[][] temp = new int[MAX_N][];private int k;public int[][] sortTheStudents(int[][] score, int k) {this.k = k;mergeSort(score);return score;}// 归并操作,入参改成二维数组private void merge(int[][] arr, int left, int mid, int right) {int index1 = left, index2 = mid + 1, index = left;while(index1 <= mid && index2 <= right) {// 除了收集元素的标准不一样,其它都可以不变temp[index++] = arr[index1][k] > arr[index2][k] ? arr[index1++] : arr[index2++];}while(index1 <= mid) {temp[index++] = arr[index1++];}while(index2 <= right) {temp[index++] = arr[index2++];}System.arraycopy(temp, left, arr, left, right - left + 1);}// 归并排序,入参改成二维数组private void mergeSort(int[][] arr) {int n = arr.length;for(int left, mid, right, step = 1; step < n; step <<= 1) {left = 0;while(left < n) {mid = left + step - 1;if(mid >= n - 1) {break;}right = Math.min(left + (step << 1) - 1, n - 1);merge(arr, left, mid, right);left = right + 1;}}}
}
随机快速排序
class Solution {private static int k;private static int first, last;public int[][] sortTheStudents(int[][] score, int k) {this.k = k;quickSort(score, 0, score.length - 1);return score;}// 交换操作,入参改成二维数组private void swap(int[][] arr, int i, int j) {int[] temp = arr[i];arr[i] = arr[j];arr[j] = temp;}// 划分操作,入参改成二维数组private void partition(int[][] arr, int left, int right, int pivot) {first = left;last = right;int cur = left;while (cur <= last) {if (arr[cur][k] == pivot) {cur++;// 修改区域标准,较大的数往数组左侧交换} else if (arr[cur][k] > pivot) {swap(arr, first++, cur++);} else {swap(arr, cur, last--);}}}// 随机快排,入参改成二维数组private void quickSort(int[][] arr, int left, int right) {if (left >= right) {return;}int pivot = arr[left + (int) (Math.random() * (right - left + 1))][k];partition(arr, left, right, pivot);quickSort(arr, left, first - 1);quickSort(arr, last + 1, right);}
}
堆排序
class Solution {private int k;public int[][] sortTheStudents(int[][] score, int k) {this.k = k;heapSort(score);return score;}// 交换操作,入参改成二维数组private void swap(int[][] arr, int i, int j) {int[] temp = arr[i];arr[i] = arr[j];arr[j] = temp;}private void downAdjust(int[][] arr, int cur, int size) {int child = 2 * cur + 1;while (child < size) {// 修改确定修改目标的条件,用小根堆来完成排序,就能得到从大到小的结果int target = child + 1 < size && arr[child + 1][k] < arr[child][k] ? child + 1 : child;target = arr[target][k] < arr[cur][k] ? target : cur;if (target == cur) {break;}swap(arr, target, cur);cur = target;child = 2 * cur + 1;}}// 建堆操作,入参改成二维数组private void buildHeap(int[][] arr) {int n = arr.length;for (int i = n - 1; i >= 0; i--) {downAdjust(arr, i, n);}}// 堆排序,入参改成二维数组private void heapSort(int[][] arr) {buildHeap(arr);int size = arr.length;while (size > 0) {swap(arr, 0, --size);downAdjust(arr, 0, size);}}
}
总结梳理
Java 中的排序 API 的实现是 Tim Sort,大体上可以理解为在数据量较小的情况下使用 插入排序,通常使用归并排序。这里表现出来的效率不如直接实现的归并排序,猜想是因为整体数据量不是很大,在某些样例上被忽悠使用了效率不是那么高的算法。
归并排序 能够保证时间复杂度在 O ( N l o g N ) O(NlogN) O(NlogN) 这个量级的同时,算法本身是稳定的,是有必要自己实现排序算法时的首选,只需要考虑开辅助数组会不会影响效率。
快速排序 不仅需要额外的系统栈空间,还不稳定。它有时会成为面试时手撕算法的考题,需要好好掌握。
堆排序 是一种原地算法,但是不稳定,所以通常不是一个好的排序算法的选择。但是堆本身能够维护一系列元素中的最大值或者最小值,是一种非常好用的数据结构。
相关文章:
【Leetcode 每日一题】2545. 根据第 K 场考试的分数排序
问题背景 班里有 m m m 位学生,共计划组织 n n n 场考试。给你一个下标从 0 0 0 开始、大小为 m n m \times n mn 的整数矩阵 s c o r e score score,其中每一行对应一位学生,而 s c o r e [ i ] [ j ] score[i][j] score[i][j] 表示…...
一文速通 IIC I2C子系统驱动 通信协议原理 硬件 时序 深度剖析
本文作为一个引入,作用是让读者理解熟知IIC协议关键内容,结合实际手册内容,深度解析协议本质,作为后续嵌入式linux驱动IIC子系统的一个铺垫。 目录 1. 硬件连接 2. IIC传输时序 2.1.写操作 2.2.读操作 2.3.I2C信号 3.IIC协议…...
HarmonyOS(72)事件拦截处理详解
事件拦截 1、参考资料2、HitTestMode3、onTouchIntercept、onTouch、onClick事件执行顺序3.1、系统默认事件传递顺序3.2、子组件拦截事件1、参考资料 HarmonyOS(71) 自定义事件分发之TouchTestStrategy使用说明HarmonyOS(70) ArkUI 事件分发拦截,事件冲突解决方案HitTestModea…...
docker(wsl)命令 帮助文档
WSL wsl使用教程 wsl -l -v 列出所有已安装的 Linux 发行版 wsl -t Ubuntu-22.04 --shutdown 关闭所有正在运行的WSL发行版。如果你只想关闭特定的发行版 wsl -d Ubuntu-22.04 登录到Ubuntu环境 wsl --list --running 查看正在wsl中运行的linux发行版 wsl --unregister (系统名…...
nginx 拦截指定ip访问指定 url
nginx 拦截指定ip访问指定 url 这里需要注意的是一定要用$http_x_forwarded_for 这个变量 upstream myapp1 { # 定义一个名为myapp1的服务器组 server backend1.example.com weight5; # 添加一个服务器,并设置权重为5 server backend2.example.com; # 添加另…...
git仓库的基本概念和流程以及一些基本命令
什么是版本库?版本库又名仓库,英文名repository,你可以简单的理解一个目录,这个目录里面的所有文件都可以被Git管理起来,每个文件的修改,删除,Git都能跟踪,以便任何时刻都可以追踪历史ÿ…...
Intel-ECI之Codesys PLC + Ethercat 远端IO + Codesys IDE编程
目录 一、 准备工作 二、安装Codesys 软件 PLC 三、 使用Codesys IDE 编程测试 CODESYS* 是领先的独立于制造商的 IEC 61131-3 自动化软件,适用于工程控制系统。它用于 Intel Edge Controls for Industrial(Intel ECI 或 ECI),…...
互联网医院系统,互联网医院系统源码可供
互联网医院系统开发,其功能特点和优势在于实现了线上医疗服务与信息技术的深度融合。此系统旨在构建一个更为高效、便捷的医疗服务平台,提升患者的就医体验和医疗服务的效率。 一、功能特点 1、预约挂号与在线咨询 患者可通过系统进行预约挂号…...
Marin说PCB之POC电路layout设计仿真案例---06
我们书接上回啊,对于上面的出现原因我这个美女同事安娜说会不会你把POC电感下面的相邻两层的CUT_OUT的尺寸再去加大一些会不会变得更好呢?这个难道说是真的有用吗?小编我先自己算一卦看下结果。 本期文章我们就接着验证通过改善我们的单板POC…...
windwos defender实现白名单效果(除了指定应用或端口其它一律禁止)禁止服务器上网
一、应用场景说明 当我们的一台windows服务器中毒,变成别人肉鸡,不断向外请示非法网站或攻击其它服务器。 要彻底清除相关木马或病毒往往需要的时间比较长,比较有效的方法是禁止服务器主动向外发包除了网站端口和远程程序除外。 其实这就是一…...
Fiddler勾选https后google浏览器网页访问不可用
一、说明 最近电脑重新安装系统后,之前的所有工具都需要重新安装和配置,有个项目需要抓包https包查看一下请求的内容,通过Fiddler工具,但是开启后,发现https的无法抓取,同时google浏览器也不无法访问互联网…...
机器视觉检测相机基础知识 | 颜色 | 光源 | 镜头 | 分辨率 / 精度 / 公差
注:本文为 “keyence 视觉沙龙中机器视觉检测基础知识” 文章合辑。 机器视觉检测基础知识(一)颜色篇 视觉检测硬件构成的基本部分包括:处理器、相机、镜头、光源。 其中,和光源相关的最重要的两个参数就是光源颜色和…...
解决pytorch安装中的三个错误
查明已安装python版本为3.12.7后,创建虚拟环境。 报错内容:ArgumentError: one of the arguments -n/–name -p/–prefix is required 解决方式: 输入 conda create -n pytorch python3.8即可安装成功。 参考文章:https://blo…...
用Python开发高级游戏:实现3D迷宫游戏
Python虽然被认为是一门简单易学的语言,但它在游戏开发领域同样具有强大的潜力,尤其是结合诸如Pygame、Panda3D、PyOpenGL等框架,可以开发出复杂的游戏。 在本文中,我们将通过一个示例,介绍如何使用Python开发一个高级3D迷宫游戏。本文使用的框架是 Panda3D,一个专为3D游…...
基于 uniapp 开发 android 播放 webrtc 流
一、播放rtsp协议流 如果 webrtc 流以 rtsp 协议返回,流地址如:rtsp://127.0.0.1:5115/session.mpg,uniapp的 <video> 编译到android上直接就能播放,但通常会有2-3秒的延迟。 二、播放webrtc协议流 如果 webrtc 流以 webrt…...
Unity引擎学习总结------动画控件
左侧窗格可以在参数视图和图层视图之间切换。参数视图允许您创建、查看和编辑动画控制器参数。这些是您定义的变量,用作状态机的输入。要添加参数,请单击加号图标并从弹出菜单中选择参数类型。要删除参数,请在列表中选择该参数并按删除键&…...
Pytorch | 从零构建GoogleNet对CIFAR10进行分类
Pytorch | 从零构建GoogleNet对CIFAR10进行分类 CIFAR10数据集GoogleNet网络结构特点网络整体架构应用与影响Inceptionv1到Inceptionv2 GoogleNet结构代码详解结构代码代码详解Inception 类初始化方法前向传播 forward GoogleNet 类初始化方法前向传播 forward 训练过程和测试结…...
基于SIFT的目标识别算法
基于SIFT(Scale-Invariant Feature Transform)的目标识别算法是一种经典的计算机视觉算法,用于在图像中寻找和匹配具有尺度不变性的特征点,从而实现目标的快速而准确的识别。 SIFT算法的主要步骤包括以下几个阶段: 尺…...
计算机组成原理的学习笔记(4)--数据的表示与运算·其三 补码的乘法以及原码补码的除法
学习笔记 前言 本文主要是对于b站尚硅谷的计算机组成原理的学习笔记,仅用于学习交流。 1.补码乘法 基本操作 与正常原码乘法差不多,逐位乘,随后相加,而与符号位有关的一项也叫校正项 Booth算法 从乘数的最低位开始,…...
压缩glb模型文件
使用?gltf-pipeline进行压缩: GitHub地址[这里是图片001]https://github.com/CesiumGS/gltf-pipeline 1. 安装gltf-pipeline npm install -g gltf-pipeline2. 在glb文件目录打开cmd进行命令行压缩: // cmd: gltf-pipeline -i glb.glb -d -s以下是 -…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...
机器学习的数学基础:线性模型
线性模型 线性模型的基本形式为: f ( x ) ω T x b f\left(\boldsymbol{x}\right)\boldsymbol{\omega}^\text{T}\boldsymbol{x}b f(x)ωTxb 回归问题 利用最小二乘法,得到 ω \boldsymbol{\omega} ω和 b b b的参数估计$ \boldsymbol{\hat{\omega}}…...
