leetcode-74-搜索二维矩阵
leetcode-74-搜索二维矩阵
chenjx85
发布于 2018-08-30 17:21:08
发布于 2018-08-30 17:21:08
题目描述：
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true示例 2:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false要完成的函数：
bool searchMatrix(vector<vector<int>>& matrix, int target)
说明：
1、这道题给定一个m行n列的矩阵，要求编写一个高效的算法来判断矩阵中是否含有target这个元素。
如果存在，返回true，否则返回false。
2、这道题其实就是二分法在矩阵上的应用，整个矩阵是升序的。
我们先用二分法确定target可能会在哪一行，接着再用二分法确定target在哪一列，或者不存在。
代码如下：（附详解）
bool searchMatrix(vector<vector<int>>& matrix, int target)
{
if(matrix.size()==0||matrix[0].size()==0)return false;//[]或者[[]]的边界条件
int hang=matrix.size(),lie=matrix[0].size(),left=0,right=hang-1,med,t;
while(left<=right)//二分法判断target在哪一行
{
med=(left+right)/2;
if(target<matrix[med][0])
right=med-1;
else if(target>matrix[med][lie-1])
left=med+1;
else//找到元素在med这一行了
{
t=med;
left=0;
right=lie-1;
while(left<=right)//用二分法找到target在哪一列
{
med=(left+right)/2;
if(matrix[t][med]==target)//找到了返回true
return true;
else if(target<matrix[t][med])
right=med-1;
else
left=med+1;
}
return false;//target大于当前行最后一个元素或者小于第一个元素，返回false
}
}
return false;//target小于矩阵的第一行第一个元素，或者大于矩阵最后一行最后一个元素，返回false
}上述代码实测8ms，beats 97.83% of cpp submissions。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-08-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录