西安网站开发的空间,上海网站建设公司四叶互联,页游和做网站,平顶山城市建设局网站文章目录 写在前面Tag题目来源题目解读解题思路方法一#xff1a;二分查找 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主#xff0c;并附带一些对于本题涉及到的数据结构等… 文章目录 写在前面Tag题目来源题目解读解题思路方法一二分查找 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【二分查找】【数组】 题目来源
74. 搜索二维矩阵 题目解读
在二维矩阵中查找指定值如果存在返回 true否则返回 false。 解题思路
方法一二分查找
二维矩阵每行是有序的每一行的第一个整数都是大于上一行的最后一个整数的那么吧二维矩阵 “拉直” 形成一维数组这个数组也是有序的那么本题就转化为在有序数组中判断是否存在指定值妥妥的可以使用二分查找来完成。
“拉直” 指的是将矩阵按行进行拼接得到一个一维数组下标为二维坐标与一维数的一一映射的值。比如二维矩阵第 i 行第 j 列用 i * m jm 为二维矩阵的列数来表示对应的知道一维的值 x 可以求出对应的二维矩阵的坐标 (x / m, x % m)。
接着在一维数组中进行二分查找即可
初始化指针 l 0, r m * n - 1l r 时进行 while 循环判断当前的二分中点 mid (r - l) / 2 l对应二维矩阵中的值为 x matrix[mid / m][mid % m] 如果 x target更新 l mid 1如果 x target更新 r mid - 1否则说明查找到 target直接返回 true 如果退出 while 循环仍然没有找到 target直接返回 false。
实现代码
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {int n matrix.size(), m matrix[0].size();int l 0, r m * n - 1;int mid;while(l r){mid (l r) 1;int x matrix[mid / m][mid % m];if(target x){l mid 1;}else if(target x){r mid - 1;}else{return true;}}return false;}
};复杂度分析
时间复杂度 O ( n m ) O(nm) O(nm) n n n 和 m m m 分别为二维矩阵的高度和宽度。
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
