搜索二维矩阵[中等]

news/2024/4/17 17:27:09

一、题目

给你一个满足下述两条属性的m x n整数矩阵:
【1】每行中的整数从左到右按非严格递增顺序排列。
【2】每行的第一个整数大于前一行的最后一个整数。

给你一个整数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

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

二、代码

【1】两次二分查找: 由于每行的第一个元素大于前一行的最后一个元素,且每行元素是升序的,所以每行的第一个元素大于前一行的第一个元素,因此矩阵第一列的元素是升序的。

我们可以对矩阵的第一列的元素二分查找,找到最后一个不大于目标值的元素,然后在该元素所在行中二分查找目标值是否存在。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int low = 0, high = m * n - 1;while (low <= high) {int mid = (high - low) / 2 + low;int x = matrix[mid / n][mid % n];if (x < target) {low = mid + 1;} else if (x > target) {high = mid - 1;} else {return true;}}return false;}
}

时间复杂度: O(log ⁡m+log ⁡n)=O(log ⁡mn),其中mn分别是矩阵的行数和列数。
空间复杂度: O(1)

【2】一次二分查找: 若将矩阵每一行拼接在上一行的末尾,则会得到一个升序数组,我们可以在该数组上二分找到目标元素。代码实现时,可以二分升序数组的下标,将其映射到原矩阵的行和列上。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int low = 0, high = m * n - 1;while (low <= high) {int mid = (high - low) / 2 + low;int x = matrix[mid / n][mid % n];if (x < target) {low = mid + 1;} else if (x > target) {high = mid - 1;} else {return true;}}return false;}
}

时间复杂度: O(log⁡mn),其中mn分别是矩阵的行数和列数。
空间复杂度: O(1)

两种方法殊途同归,都利用了二分查找,在二维矩阵上寻找目标值。值得注意的是,若二维数组中的一维数组的元素个数不一,方法二将会失效,而方法一则能正确处理。


https://www.xjx100.cn/news/3271418.html

相关文章

Linux第50步_移植ST公司的linux内核第2步_编译ST公司的linux源码和修改网络驱动

1、修改“linux-5.4.31”目录下的“Makefile” 1)、使用VSCode打开“linux-5.4.31.code-workspace” 2)、点击“linux-5.4.31”目录下的“Makefile” 3)、点击“编辑”&#xff0c;点击“查找”&#xff0c;输入“CROSS_COMPILE回车”&#xff0c;找到“ARCH ? $(SUBARCH)”…

Transformer实战-系列教程16:DETR 源码解读3(DETR类)

&#x1f6a9;&#x1f6a9;&#x1f6a9;Transformer实战-系列教程总目录 有任何问题欢迎在下面留言 本篇文章的代码运行界面均在Pycharm中进行 本篇文章配套的代码资源已经上传 点我下载源码 DETR 算法解读 DETR 源码解读1&#xff08;项目配置/CocoDetection类&#xff09; …

单页404源码

<!doctype html> <html> <head> <meta charset"utf-8"> <title>简约 404错误页</title><link rel"shortcut icon" href"./favicon.png"><style> import url("https://fonts.googleapis.co…

c++恶魔轮盘制造第1期输赢

小常识&#xff0c;恶魔叫DEALER&#xff0c;上帝叫God. 赢了很简单 void sheng() { cout<<"你获胜了&#xff01;";MessageBox(NULL,TEXT("你的钱~~~~~~给你"),TEXT("DEALER"),MB_OK);system("pause");system("cls"…

powershell 雅地关闭UDP监听器

在PowerShell中优雅地关闭UDP监听器意味着你需要一种机制来安全地停止正在运行的UdpClient实例。由于UdpClient类本身没有提供直接的停止或关闭方法&#xff0c;你需要通过其他方式来实现这一点。通常&#xff0c;这涉及到在监听循环中添加一个检查点&#xff0c;以便在接收到停…

使用 C++23 从零实现 RISC-V 模拟器(1):最简CPU

&#x1f449;&#x1f3fb; 文章汇总「从零实现模拟器、操作系统、数据库、编译器…」&#xff1a;https://okaitserrj.feishu.cn/docx/R4tCdkEbsoFGnuxbho4cgW2Yntc 本节实现一个最简的 CPU &#xff0c;最终能够解析 add 和 addi 两个指令。如果对计算机组成原理已经有所了…

MySQL篇----第十四篇

系列文章目录 文章目录 系列文章目录前言一、MySQL 数据库作发布系统的存储,一天五万条以上的增量,预计运维三年,怎么优化?二、锁的优化策略三、索引的底层实现原理和优化四、什么情况下设置了索引但无法使用前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽…

模态、模式和真实发生

模态和模式均是用来描述某一对象或系统可能出现的特性、状态或行为&#xff0c;它们既包括逻辑上的抽象可能性&#xff0c;也涵盖现实中具体的现象和事件结构。模态更多地关联于逻辑可能性和必然性&#xff0c;而模式则侧重于现象的重复性和规律性&#xff0c;两者都可以反映真…