华为OD技术面试-有序数组第K最小值
背景
2024-03-15华为od 二面,记录结题过程
- 有序矩阵中第 K 小的元素 - 力扣(LeetCode) https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/submissions/512483717/
题目
给你一个 n x n 矩阵 matrix ,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。 请注意,它是 排序后 的第 k 小元素,而不是第 k 个 不同 的元素。
你必须找到一个内存复杂度优于 O(n2) 的解决方案。
示例 1:
输入:matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 输出:13
解释:矩阵中的元素为 [1,5,9,10,11,12,13,13,15],第 8 小元素是 13
分析
采用遍历的思路
这里有个特点
- 如果已有第m小,则红色部分必须都已排好序,且连续
- 且下一个 小的数,只能是 黄色部分

结果

代码
class Solution(object):def kthSmallest(self, matrix, k):""":type matrix: List[List[int]]:type k: int:rtype: int"""n = len(matrix)self.n = nself.matrix = matrixikx = {}for i in range(n):ikx[i] = [i, -1]iix = [] # 当前遍历点ik = 0 # 当前第N小while True:ikx2 = self.get_maymin_iix(ikx)if len(ikx2)==1:iix = list(ikx2.values())[0][0]else:iix = min(ikx2.items(), key=lambda x:x[1][1])[1][0]ik += 1x, y = iixikx[x][1] = yif ik ==k :return matrix[iix[0]][iix[1]]def get_maymin_iix(self, ikx):ikx2 = {}for i,point in ikx.items():x, y = pointif y>=self.n-1:continuey = y+1if i>=1 and ikx[i-1][1]<y:continueikx2[i] = [(x, y),self.matrix[x][y]]return ikx2
测试
matrix = [[1,5,9],[10,11,13],[12,13,15]]c = {0: [(0, 1), 5], 1: [(1, 0), 10]}c = Solution()c.kthSmallest(matrix, 8)
相关文章:
华为OD技术面试-有序数组第K最小值
背景 2024-03-15华为od 二面,记录结题过程 有序矩阵中第 K 小的元素 - 力扣(LeetCode) https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/submissions/512483717/ 题目 给你一个 n x n 矩阵 matrix ,其…...
idea如何debug看springsecurity的过滤器顺序
idea如何debug看springsecurity的过滤器顺序 先配置一个Spring启动对象,后续需要根据这个对象来获取SpringSecurity的过滤器链 设置一个输出信息,需要在输出信息这里打上断点,才方便查看过滤器链 public static void main(String[] args) {//此时不…...
【力扣】125.验证回文串
刷题,过了真的好有成就感!!! 题解: 根据题目要求,我们需要处理一下几个问题: 将大写字母转变成小写对原来的字符串进行处理,只要字母和数字考虑只有一个和字符串为空的情况 1、将…...
Fantasy Map Creator 2
Fantasy Map Creator 2是一组风格化的图像,用于在图形编辑器中创建完整的彩色地图或游戏位置,无需艺术技能或图形平板电脑。 Fantasy Map Creator 2是一组风格化的图像,用于在图形编辑器中创建完整的彩色地图或游戏位置,无需艺术技能或图形平板电脑。 现在,每个人都可以在…...
什么是云原生
什么是云原生 云原生的定义 aws: 云原生是在云计算环境中构建、部署和管理现代应用程序的软件方法。现代公司希望构建高度可伸缩、灵活和有弹性的应用程序,以便能够快速更新以满足客户需求。为此,他们使用了支持云基础设施上应用程序开发的现…...
为什么要“挺”鸿蒙?
鸿蒙到底是什么? 随着5G、物联网等技术的快速发展,智能终端设备的应用场景也越来越广泛。为了满足不同设备间的互联互通需求,华为在2019年推出了自主研发的操作系统——鸿蒙OS。值得关注的是,这也是首款国产操作系统。 要了解鸿…...
去掉el-date-picker弹窗默认回显当前月份的方法
打开日期弹窗,默认会显示当前月份,如图 会发现加了穿透::v-deep 样式也不生效 .el-month-table .today .cell {color: pink;font-weight: 400;}要让 popper-class“xclass” :append-to-body“false” 这俩配合着使用…...
绝地求生:PUBG×杜卡迪联名上线!参与投稿评论赢取精美好礼
PUBG杜卡迪联名活动游戏内现已正式上线!我们诚邀与您一起在开拓未知战场和书写新历史的过程中,与杜卡迪一同实现您的极速梦想! 在本次的杜卡迪工坊中,更是包含了具备标志性红色在内的6种颜色供您自由选择,一起自由驰骋…...
10个大型语言模型(LLM)常见面试问题和答案解析
今天我们来总结以下大型语言模型面试中常问的问题 1、哪种技术有助于减轻基于提示的学习中的偏见? A.微调 Fine-tuning B.数据增强 Data augmentation C.提示校准 Prompt calibration D.梯度裁剪 Gradient clipping 答案:C 提示校准包括调整提示,尽量减少产生…...
rollup 插件架构-驱动设计 PluginDriver
文章目录 GraphPluginDriver生成 PluginDriver 实例和 PluginCache 缓存创建插件上下文 pluginContext初始化 pluginContext 缓存设置、方法插件中使用缓存可替换的 replace pluginContextPluginDriver 提供 asyn、first、parallel 等类型 hookgetSortedPlugins 运行时收集并存…...
netty实现mqtt(IOT)
springbootnettymqtt服务端实现 springbootnettymqtt客户端实现 MQTT协议基本讲解(结合netty) 李兴华netty视频教程中mqtt讲解 EMQX官网、mqttx客户端 IOT云平台 simple(6)springboot netty实现IOT云平台基本的架构(mqtt、Rabbitmq&…...
基于STC12C5A60S2系列1T 8051单片机的液晶显示器LCD1602显示汉字的功能
基于STC12C5A60S2系列1T 8051单片机的液晶显示器LCD1602显示汉字的功能 STC12C5A60S2系列1T 8051单片机管脚图STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式及配置STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式介绍LCD1602字符型液晶显示器介绍一、LCD1602字符型…...
Springboot+Redis:实现缓存 减少对数据库的压力
🎉🎉欢迎光临,终于等到你啦🎉🎉 🏅我是苏泽,一位对技术充满热情的探索者和分享者。🚀🚀 🌟持续更新的专栏Redis实战与进阶 本专栏讲解Redis从原理到实践 …...
springboot组件的单例模式和分布式分析
springboot组件的单例模式和分布式分析 一、基本概念 在Spring Boot应用中,单例模式是非常常见的一种设计模式,它被广泛应用于Bean的生命周期管理。Spring容器默认会将所有的Component、Service、Repository和Controller注解标记的类作为单例对象进行实…...
Linux:zip命令介绍
简介 zip命令可以用来解压缩文件,或者对文件进行打包操作。zip是个使用广泛的压缩程序,文件经它压缩后会另外产生具有“.zip”扩展名的压缩文件。 语法 zip [选项] [参数] 选项 -A:调整可执行的自动解压缩文件; -b<工作目录&g…...
远程桌面无法连接怎么办?
远程桌面无法连接是指在尝试使用远程桌面功能时出现连接失败的情况。这种问题可能会给工作和生活带来极大的不便,因此我们需要寻找解决办法。在讨论解决方案之前,我们先来了解一下【天联】组网的优势。 【天联】组网的优势有很多。它能够解决复杂网络环境…...
HarmonyOS实战开发-拼图、如何实现获取图片,以及图片裁剪分割的功能。
介绍 该示例通过ohos.multimedia.image和ohos.multimedia.mediaLibrary接口实现获取图片,以及图片裁剪分割的功能。 效果预览 使用说明: 使用预置相机拍照后启动应用,应用首页会读取设备内的图片文件并展示获取到的第一个图片,…...
【LeetCode热题100】【二叉树】二叉树的最近公共祖先
题目链接:236. 二叉树的最近公共祖先 - 力扣(LeetCode) 二叉树皆可递归,可以递归查找两个节点的所在地,如果两个节点一个在root的左子树一个在右子树,说明root就是公共祖先,并且因为是递归&…...
动态规划专练( 1049.最后一块石头的重量Ⅱ)
1049.最后一块石头的重量Ⅱ 有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x < y。那么粉碎的可能结果如…...
2024年最佳WordPress插件
我喜欢的最佳WordPress插件(也是经验丰富的WordPress开发者强烈推荐的)。所有这些插件都是编码干净、超快且一流的。我还包括了对我不喜欢的插件的想法……只为了让你有进一步的了解。 目录 隐藏 1 古腾堡块: 2 内容: 3 缓存…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...
CSS3相关知识点
CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...
新版NANO下载烧录过程
一、序言 搭建 Jetson 系列产品烧录系统的环境需要在电脑主机上安装 Ubuntu 系统。此处使用 18.04 LTS。 二、环境搭建 1、安装库 $ sudo apt-get install qemu-user-static$ sudo apt-get install python 搭建环境的过程需要这个应用库来将某些 NVIDIA 软件组件安装到 Je…...
使用ch340继电器完成随机断电测试
前言 如图所示是市面上常见的OTA压测继电器,通过ch340串口模块完成对继电器的分路控制,这里我编写了一个脚本方便对4路继电器的控制,可以设置开启时间,关闭时间,复位等功能 软件界面 在设备管理器查看串口号后&…...
