LeetCode 378 有序矩阵中第K小的元素

题目信息

LeetoCode地址: . - 力扣(LeetCode)

题解内容大量转载于:. - 力扣(LeetCode)

题目理解

题意很直观,就是求二维矩阵中所有元素排序后第k小的数。

最小堆写法

该写法不再赘述,维护一个大小为k的小顶堆,遍历矩阵所有元素进行入堆操作。

时间复杂度:O(nlogk)

空间复杂度:O(k)

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> (int)b-(int)a);
        for (int i = 0; i<matrix.length; i++) {
            for (int j = 0; j<matrix[0].length;j++) {
                if (heap.size() < k) {
                    heap.offer(matrix[i][j]);
                } else if (matrix[i][j] < heap.peek()) {
                    heap.poll();
                    heap.offer(matrix[i][j]);
                }
            }
        }
        return heap.peek();

    }
}

二分写法

由于矩阵在行和列上都是有序的,因此左上角的元素matrix[0][0]一定是最小的,右下角的元素matrix[n-1][n-1]一定是最大的。这两个元素,我们分别记为l 和 r.

以下图为例:

可以发现, 任取一个数mid满足l<=mid<=r, 那么矩阵中不大于mid的数,肯定都分布在矩阵的左上角。

例如下图, 取mid=8:

我们可以看出,矩阵中大于mid的数和不大于mid的数分别形成了两个版本,沿着一条锯齿线将这个矩形分隔开。其中左上角板块的大小即为不大于mid的数的数量。

我们只需沿着这条锯齿线走一遍即可计算出这两个板块的大小,自然就统计出这个矩阵中不大于mid的数的个数了。

同样以mid=8举例,走法如下:

走法可以总结如下:

  • 初始位置在matrix[n-1][0] (即左下角);
  • 设当前位置为matrix[i][j], 若matrix[i][j] <= mid, 则将当前所在列的不大于mid的数的数量(即i+1)累加到答案中,并向右移动,否则向上移动;
  • 不断移动,直到走出格子为止。

可以发现,这样的走法时间复杂度为O(n),即我们可以线性的计算对于任意一个mid,矩阵中有多少数不大于它。这满足了二分查找的性质。

不妨设答案为x, 那么可以直到l<=x<=r, 这样就确定了二分查找的上下界。

对于每次猜测的答案mid, 计算矩阵中有多少数不大于 mid:

  • 如果数量不少于k, 那么说明最终答案不大于mid;
  • 如果数量小于k, 那么说明最终答案大于mid.

这样我们就可以计算出最终的结果x了。

时间复杂度: O(nlogn)

额外空间复杂度: O(1)

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int h = matrix.length, w = matrix[0].length;
        int l = matrix[0][0], r = matrix[h-1][w-1];
        while (l < r) {
            int mid = l + (r-l)/2;
            if (check(matrix, mid, k)) {
                r = mid;
            } else {
                l = mid+1;
            }
        }
        return l;
    }
    public boolean check(int[][] matrix,int mid, int k) {
        int i = matrix.length-1, j = 0;
        int count = 0;
        while (i >=0 && j < matrix[0].length) {
            if (matrix[i][j] <= mid) {
                count += i+1;
                j++;
            } else {
                i--;
            }
        }
        return count >= k; 
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/521410.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

simulink的硬件支持下,串口发送的模型,stm32f407的串口程序调试错误

串口调试助手能接收到数据&#xff0c;为何是8个数据&#xff1f;如之奈何&#xff1f; 参考文章&#xff1a; STM32CubeMxMATLAB Simulink串口输出实验_用stm32cubemx生成的串口都是输出-CSDN博客根据 该文章发送字符串 hello&#xff0c;发送数量为5&#xff0c;接收也是he…

解读命令:icacls “E:\ShareAll“ /grant “Everyone:(OI)(CI)(F)“

命令 icacls "E:\ShareAll" /grant "Everyone:(OI)(CI)(F)" 是在Windows操作系统中用来修改文件或目录权限的命令行操作。该命令执行以下操作&#xff1a; 路径&#xff1a;"E:\ShareAll" 指定了要更改权限的目录位置&#xff0c;即对E盘下的“S…

Cisco Packet Tracer配置AAA认证

出口路由器R1配置&#xff1a; ip domain-name cisco.com;写入设备的默认域名 crypto key generate rsa;产生rsa密钥 ip ssh secret cisco;启用ssh服务 enable secret cisco;设置特权模式密码 连接TACAS的路由器做同样配置 RADIUS服务器的配置 client ip 配置成RADIUS服务器…

二分法题集2

目录 1 山脉数组的峰顶索引 分析&#xff1a; 代码展示&#xff1a; 2 寻找峰值 分析&#xff1a; 代码展示&#xff1a; 3 寻找旋转排序数组中的最小值 分析&#xff1a; 代码展示&#xff1a; 4 点名 分析&#xff1a; 代码展示&#xff1a; 1 山脉数组的峰顶…

数据结构学习——栈和队列

1.栈 1.1栈的概念及结构 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO&#xff08;Last In First Out&#xff09;的原则。 …

《BERT》论文笔记

原文链接&#xff1a; [1810.04805] BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding (arxiv.org) 原文笔记&#xff1a; What&#xff1a; BETR&#xff1a;Pre-training of Deep Bidirectional Transformers for Language Understand…

Ruoyi-vue-pro Vue + nginx 二级目录部署到云服务器

http://www.your-server.com/ 这是一级目录&#xff0c;由于项目多&#xff0c;一般会通过二级域名http://oa.your-server.com/或二级目录http://www.your-server.com/oa来发布&#xff0c;本篇记录一下二级目录发布。先看效果 1、router/index.js配置base export default new …

对代理模式的理解

目录 一、前言二、案例1 代码2 自定义代理类【静态代理】2.1 一个接口多个实现&#xff0c;到底注入哪个依赖呢&#xff1f;2.1.1 Primary注解2.1.2 Resource注解&#xff08;指定name属性&#xff09;2.1.3 Qualifier注解 2.2 面向接口编程2.3 如果没接口咋办呢&#xff1f;2.…

算法基础课-搜索与图论

DFS 题目链接&#xff1a;842. 排列数字 - AcWing题库 思路&#xff1a;写的很好的题解AcWing 842. 排列数字--深度优先遍历代码注释 - AcWing #include<bits/stdc.h>using namespace std; int n; int st[10]; vector<int> a; void dfs(){if(a.size() n){for(in…

python标准数据类型--集合常用方法

在Python中&#xff0c;集合&#xff08;Set&#xff09;是一种无序且不重复的数据结构&#xff0c;它是由一个无序的、不重复的元素组成的。Python中的集合与数学中的集合概念相似&#xff0c;并且支持一系列常用的方法。本篇博客将深入介绍Python集合的常用方法&#xff0c;帮…

c# wpf XmlDataProvider 简单试验

1.概要 2.代码 <Window x:Class"WpfApp2.Window12"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.microsoft.com/expression/blend…

【C++初阶】String在OJ中的使用(一):仅仅反转字母、字符串中的第一个唯一字母、字符串最后一个单词的长度、验证回文串、字符串相加

前言&#xff1a; &#x1f3af;个人博客&#xff1a;Dream_Chaser &#x1f388;博客专栏&#xff1a;C &#x1f4da;本篇内容&#xff1a;仅仅反转字母、字符串中的第一个唯一字母、字符串最后一个单词的长度、验证回文串、字符串相加 目录 917.仅仅反转字母 题目描述&am…

C#操作MySQL从入门到精通(5)——查询数据

前言 在和MySql数据库交互的过程中,查询数据是使用最频繁的操作,本文详细介绍了查询数据的各种操作,包括查询一列数据、 查询两列数据、查询所有列数据、查询不重复的数据、查询指定行数据,绝对是C#操作MySql数据库史上最详细教程,能够帮助小白快速入门以及将这些功能迅速…

【数据结构】考研真题攻克与重点知识点剖析 - 第 3 篇:栈、队列和数组

前言 本文基础知识部分来自于b站&#xff1a;分享笔记的好人儿的思维导图与王道考研课程&#xff0c;感谢大佬的开源精神&#xff0c;习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析&#xff0c;本人技术…

阿里云2核2G和2核4G轻量应用服务器优惠价格表,2024年最新报价

阿里云轻量应用服务器2核2G和2核4G配置优惠价格表&#xff0c;轻量2核2G3M带宽61元一年&#xff0c;轻量2核4G4M带宽165元1年&#xff0c;均不限制月流量&#xff0c;阿里云活动链接 aliyunfuwuqi.com/go/aliyun 活动打开如下图&#xff1a; 阿里云轻量应用服务器价格 61元/年…

上位机图像处理和嵌入式模块部署(qmacvisual实时视频)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 前面我们测试和练习的时候&#xff0c;大部分情况下都是利用图像进行测试的&#xff0c;但是实际情况下&#xff0c;或者准确一点说&#xff0c;工…

android 制作登录页

项目需要可以直接copy layout.xml <?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"…

【六 (2)机器学习-EDA探索性数据分析模板】

目录 文章导航一、EDA&#xff1a;二、导入类库三、导入数据四、查看数据类型和缺失情况五、确认目标变量和ID六、查看目标变量分布情况七、特征变量按照数据类型分成定量变量和定性变量八、查看定量变量分布情况九、查看定量变量的离散程度十、查看定量变量与目标变量关系十一…

软考114-上午题-【计算机网络】-路由

一、路由 二、真题 真题1&#xff1a; 真题2&#xff1a; 真题3&#xff1a; 真题4&#xff1a; 真题5&#xff1a; 路由协议实际上是一种在路由器之间交换路由信息的协议。 路由协议让路由器了解整个网络的拓扑结构&#xff0c;包括哪些网络是直接相连的&#xff0c;哪些网络…

vscode的源码插件GitHub Repositories

打铁还需自身硬&#xff0c;需要不断提升自我&#xff0c;提升自我的一种方式就是看源码&#xff0c;站在更高的维度去理解底层原理&#xff0c;以便以后更好的开发和解决问题&#xff0c;由于源码一个动不动就是几个G甚至十几个G&#xff0c;如果一个个源码下载下来&#xff0…