网站默认样式表,建设一个外贸网站需要多少钱,杂志网站建设推广方案,在线房屋设计网站文章目录1. 题目2. 解题2.1 从左下角或者右上角开始搜索2.2 分治算法1. 题目
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性#xff1a;
每行的元素从左到右升序排列。 每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下…
文章目录1. 题目2. 解题2.1 从左下角或者右上角开始搜索2.2 分治算法1. 题目
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性
每行的元素从左到右升序排列。 每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下
[[1, 4, 7, 11, 15],[2, 5, 8, 12, 19],[3, 6, 9, 16, 22],[10, 13, 14, 17, 24],[18, 21, 23, 26, 30]
]
给定 target 5返回 true。
给定 target 20返回 false。类似题目 LeetCode 74. 搜索二维矩阵二分查找 程序员面试金典 - 面试题 10.09. 排序矩阵查找
来源力扣LeetCode 链接https://leetcode-cn.com/problems/search-a-2d-matrix-ii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 从左下角或者右上角开始搜索 在左下角或者右下角以所在点形成的L形状是有序的根据大小选择走的方向时间复杂度Omn
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {if(matrix.size()0 || matrix[0].size() 0)return false;int r matrix.size(), c matrix[0].size();int x r-1, y 0;//左下角while(x0 yc){if(matrix[x][y] target)return true;else if(matrix[x][y] target)y;elsex--;}return false;}
};or
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {if(matrix.size()0 || matrix[0].size() 0)return false;int r matrix.size(), c matrix[0].size();int x 0, y c-1;//右上角while(xr y0){if(matrix[x][y] target)return true;else if(matrix[x][y] target)x;elsey--;}return false;}
};2.2 分治算法
左端点为矩阵左上角右端点为矩阵右下角按坐标取中target 比 9 大那么 下图左上角子矩阵肯定不存在在余下3块中查找(红色)target 比 9 小那么 下图右下角子矩阵肯定不存在在余下3块中查找(蓝色)时间复杂度O((m*n)的log4为底的3次幂) 近似为mn0.8 时间复杂度递推公式 O(T)3O(T/4)O(1)O(T)3O(T/4)O(1)O(T)3O(T/4)O(1)
f(T)32∗3log4(mn)≈O((mn)0.8)f(T) {3 \over 2}*{3^{\log _4^{(mn)}}} \approx O({(mn)^{0.8}})f(T)23∗3log4(mn)≈O((mn)0.8)
class Solution {int m,n;
public:bool searchMatrix(vectorvectorint matrix, int target) {if(matrix.size()0 || matrix[0].size() 0)return false;int r matrix.size(), c matrix[0].size();m r, n c;int x1 0, y1 0, x2 r-1, y2 c-1, mx, my;bool ans false;return search(matrix,target,x1,y1,x2,y2,ans);}bool search(vectorvectorint matrix, int target, int x1, int y1, int x2, int y2, bool ans){if(ans)return true;if(x1 x2 || y1 y2 ||x10||x1m||x20||x2m||y10||y1n||y20||y2n)return false;int mx x1((x2-x1)1);int my y1((y2-y1)1);if(matrix[mx][my] target){ans true;return ans;}if(matrix[mx][my] target){search(matrix,target,x1,my1,mx,y2,ans)|| search(matrix,target,mx1,y1,x2,my,ans)|| search(matrix,target,mx1,my1,x2,y2,ans);return ans;}else{search(matrix,target,x1,my,mx-1,y2,ans)|| search(matrix,target,mx,y1,x2,my-1,ans)|| search(matrix,target,x1,y1,mx-1,my-1,ans);return ans;}}
};
