力扣经典题目解析--搜索二维矩阵(小米一面)

原题地址: . - 力扣(LeetCode)

给你一个满足下述两条属性的 m x n 整数矩阵:

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。

示例 1:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true

示例 2:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false

暴力法

遍历二维数组,找到对应的数

public boolean searchMatrix(int[][] matrix, int target) {for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[i].length; j++) {if (matrix[i][j] == target) {return true;}}}return false;
}

二维二分查找

在排过序的数组中要找一个数,二分查找是效率很高的一种方式,时间复杂度是logn,二分查找的核心是定义两个指针low和high,分别对应数字开始和结尾的索引,然后找到中间的索引,判断这个中间的数与目标数的关系,大于目标数则说明目标数在左边,把high移到mid-1的位置继续找,一直到找到为止

public boolean searchMatrix(int[][] matrix, int target) {for (int i = 0; i < matrix.length; i++) {if (binarySearch(matrix[i], target) >= 0) return true;}return false;
}public static int binarySearch(int[] a, int key) {int low = 0;int high = a.length - 1;if (key < a[low] || key > a[high]) return -1;while (low <= high) {int mid = (low + high) / 2;if (a[mid] > key) {high = mid - 1;} else if (a[mid] < key) {low = mid + 1;} else {return mid;}}return -1;
}

一维二分查找

接下去上点强度,如果你能回答到这一步,这道题就达到满分了。

这道题有个条件是每行的第一个整数大于前一行的最后一个整数。也就是说把这个二维数组展开成一维数组,仍然是从小到大排序的。假设一行有n个数,则展开后的索引为idx = row * n + col.反过来,对于下标为idx的元素,对应二维数组的坐标是row = idx / n; col = idx % n;

public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length; //有多少行if (m == 0) return false;int n = matrix[0].length; // 有多少列int low = 0;// high为一维数组最后一个indexint high = m * n - 1;while (low <= high) {int mid = (low + high) / 2;//通过一维数组的index拿到二维数组的index,再拿到值int row = mid / n;int col = mid % n;if (matrix[row][col] > target) {high = mid - 1;} else if (matrix[row][col] < target) {low = mid + 1;} else {return true;}}return false;
}

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

一键生成values-sw<N>dp文件夹插件

插件名&#xff1a;SmallestWidth Dimens&#xff0c;可在AS插件中搜索安装 安装插件后&#xff0c;可使用快捷键ALTP或者在Tools|SmallestWidth 启动插件 插件启动后可自主选择要在那个moudel下生成values-sw<N>dp文件夹&#xff0c;默认有一些文件夹&#xff0c;你也…

Day 2.exec函数族和线程的基本概念、相关函数接口

exec函数族 extern char **environ; int execl(const char *path, const char *arg, ... /* (char *) NULL */); int execlp(const char *file, const char *arg, ... /* (char *) NULL */); int execle(const…

无人艇军事应用展望与思考

源自&#xff1a;《远望要报》 作者&#xff1a;赵国安 “人工智能技术与咨询” 发布 一、无人艇作战使用场景 二、军用无人艇的发展趋势 三、军用无人艇的关键技术 四、世界主要国家无人艇发展动态 结束语 声明:公众号转载的文章及图片出于非商业性的教育和科研目的供大家参…

Vue概念详解【目录】

本专栏简介&#xff1a; 这个专栏是关于 Vue2 和 Vue3 各种概念的大集合&#xff01;它深入挖掘原理&#xff0c;分析各种优势和劣势&#xff0c;适配各种应用场景&#xff0c;部分内容还列出了代码示例&#xff0c;以清晰地讲述原理。在这里&#xff0c;你将全面了解 Vue2 和…

集团机构组网

在数字化转型的浪潮中&#xff0c;企业网络需求日益复杂化&#xff0c;尤其是对于大规模的集团机构来说&#xff0c;高效、安全且可靠的网络连接成为了业务发展的关键。传统网络架构已难以满足这些需求&#xff0c;而SD-WAN&#xff08;软件定义广域网&#xff09;技术的崛起&a…

四川易点慧电子商务有限公司抖音小店:可靠的新零售典范

随着电子商务的迅猛发展和社交媒体的广泛普及&#xff0c;越来越多的消费者选择在网上购物。在这个背景下&#xff0c;四川易点慧电子商务有限公司以其独特的商业模式和强大的供应链整合能力&#xff0c;在抖音小店平台上崭露头角&#xff0c;成为了一个值得信赖的购物新选择。…

提高办公效率:Excel在文秘与行政办公中的应用技巧

&#x1f482; 个人网站:【 海拥】【神级代码资源网站】【办公神器】&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交流的小伙伴&#xff0c;请点击【全栈技术交流群】 在当今信息化时代&#xff0c;Excel作为一款常…

Python算法题集_全排列

Python算法题集_全排列 题46&#xff1a;全排列1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【标记数组递归】2) 改进版一【指针递归】3) 改进版二【高效迭代模块】4) 改进版三【高效迭代模块极简代码】 4. 最优算法5. 相关资源 本文为Python…

B树和MySql索引

1.什么是B树 它是一种平衡得多叉树&#xff0c;称为B树&#xff0c;一颗M阶的B树&#xff0c;是一颗平衡的M路的多叉树&#xff0c;可以是空树或者满足一下性质&#xff1a; 根节点至少有两个孩子。每个节点都包含k-1个关键字和K个孩子&#xff0c;其中 ceil(m/2) ≤ k ≤ m …

安泰超声功率放大器技术参数有哪些

超声功率放大器是一种用于放大超声信号的设备&#xff0c;而超声功率放大器的技术参数对于设备的性能和应用场景起着重要作用。在本文中&#xff0c;我们将介绍一些常见的超声功率放大器的技术参数。 功率输出&#xff1a;超声功率放大器的功率输出是指放大器能够输出的最大功率…

【Android移动开发】Windows10平台安装Android Studio与人工智能算法模型部署案例

目录 一、Android Studio下载地址二、开发环境JDK三、开始安装Android Studio四、案例展示与搭建五、人工智能算法模型移动端部署案例参考 一、Android Studio下载地址 https://developer.android.google.cn/studio/install.html 电脑配置要求&#xff1a; 下载保存在指定文…

3.Prometheus数据模型

采样时间戳 指标 指标值平凡也就两个字: 懒和惰; 成功也就两个字: 苦和勤; 优秀也就两个字: 你和我。 跟着我从0学习JAVA、spring全家桶和linux运维等知识&#xff0c;带你从懵懂少年走向人生巅峰&#xff0c;迎娶白富美&#xff01; 关注微信公众号【 IT特靠谱 】&#xff0…

Niginx介绍和安装使用

Nginx是什么&#xff1f; Nginx (engine x) 是一个高性能的HTTP和反向代理web服务器&#xff0c;同时也提供了IMAP/POP3/SMTP服务。Nginx是由伊戈尔赛索耶夫为俄罗斯访问量第二的Rambler.ru站点&#xff08;俄文&#xff1a;Рамблер&#xff09;开发的&#xff0c;第一…

你并不了解 JavaScript:作用域与闭包 - 第二版 - 第八章:模块化模式

第八章&#xff1a;模块化模式 在本章中&#xff0c;我们将通过探索所有编程中最重要的代码组织模式之一&#xff1a;模块&#xff0c;来结束本书的正文。正如我们将看到的那样&#xff0c;模块本质上是由我们已经讲过的内容构建而成&#xff1a;这是你学习词法作用域和闭包所…

k8s(5)

目录 使用Kubeadm安装k8s集群&#xff1a; 初始化操作&#xff1a; 每台主从节点&#xff1a; 升级内核&#xff1a; 所有节点安装docker &#xff1a; 所有节点安装kubeadm&#xff0c;kubelet和kubectl&#xff1a; 修改了 kubeadm-config.yaml&#xff0c;将其传输给…

Azure Eventhub项目引入Servicebus报NoClassDefFoundError

前提 现有项目使用azure eventhub作为IOT数据载体进行数据传输。由于业务需要&#xff0c;需要同时引入servicebus。 <dependency><groupId>com.azure</groupId><artifactId>azure-messaging-servicebus</artifactId><version>7.13.3<…

springboot网站开发-使用MultipartFile上传图片文件到远程服务器

springboot网站开发-使用MultipartFile上传图片文件到远程服务器&#xff01;昨天上午在准备网站的一些 图片&#xff0c;下午在测试图片上传的模块&#xff0c;走了一些弯路&#xff0c;今天和大家分享一下&#xff0c;免得大家再走弯路。 首先&#xff0c;要和大家声明一件事…

vue3使用echarts绘制地图

vue3使用echarts绘制地图 安装echarts npm install echarts下载地图的json数据【我这里是把json数据单独粘出来然后新建了一个文件china.json】 下载中国及各个省份的地图数据引入 import chinaJson from ./china.json绘制地图 <template><div ref"myChart&q…

面试经典150题【31-40】

文章目录 面试经典150题【31-40】76.最小覆盖字串36.有效的数独54.螺旋矩阵48.旋转图像73.矩阵置零289.生命游戏383.赎金信205.同构字符串290.单词规律242.有效的字母异位词 面试经典150题【31-40】 76.最小覆盖字串 基本思路很简单&#xff0c;就是先移动右边到合适位置。再移…

网络安全与IP安全网络安全

网络安全与IP安全网络安全 网络安全 是指网络系统的硬件&#xff0c;软件以及系统中的数据收到的保护。 保护的基本属性为&#xff1a;机密性&#xff0c;身份认证&#xff0c;完整性和可用性&#xff1b; 基本特征&#xff1a;相对性&#xff0c;时效性&#xff0c;相关性…