LeetCode 240. 搜索二维矩阵 II（二分查找 && 分治）
LeetCode 240. 搜索二维矩阵 II（二分查找 && 分治）
Michael阿明
发布于 2020-07-13 15:36:12
发布于 2020-07-13 15:36:12
文章被收录于专栏：Michael阿明学习之路
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形状是有序的，根据大小选择走的方向 - 时间复杂度O（m+n）
class Solution {
public:
bool searchMatrix(vector<vector<int>>& 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(x>=0 && y<c)
{
if(matrix[x][y] == target)
return true;
else if(matrix[x][y] < target)
y++;
else
x--;
}
return false;
}
};or
class Solution {
public:
bool searchMatrix(vector<vector<int>>& 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(x<r && y>=0)
{
if(matrix[x][y] == target)
return true;
else if(matrix[x][y] < target)
x++;
else
y--;
}
return false;
}
};
2.2 分治算法
- 左端点为矩阵左上角，右端点为矩阵右下角，按坐标取中
- target 比 9 大，那么 下图左上角子矩阵肯定不存在，在余下3块中查找(红色)
- target 比 9 小，那么 下图右下角子矩阵肯定不存在，在余下3块中查找(蓝色)
- 时间复杂度O((m*n)的log4为底的3次幂) ，近似为（mn）0.8 时间复杂度递推公式
class Solution {
int m,n;
public:
bool searchMatrix(vector<vector<int>>& 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(vector<vector<int>> &matrix, int &target, int x1, int y1, int x2, int y2, bool &ans)
{
if(ans)
return true;
if(x1 > x2 || y1 > y2 ||x1<0||x1>=m||x2<0||x2>=m||y1<0||y1>=n||y2<0||y2>=n)
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,my+1,mx,y2,ans)
|| search(matrix,target,mx+1,y1,x2,my,ans)
|| search(matrix,target,mx+1,my+1,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;
}
}
};
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/10/24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
