【LeetCode每日一题】74. 搜索二维矩阵
【LeetCode每日一题】74. 搜索二维矩阵
公众号guangcity
发布于 2021-04-22 14:57:36
发布于 2021-04-22 14:57:36
文章被收录于专栏：光城(guangcity)
【LeetCode每日一题】74. 搜索二维矩阵
今日题目74题，每日一题微信交流群可以点击右下角：合作转载->联系我，拉你入群。
题目：
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true
题解：
解法1：BST树遍历
从右上角或左边下角进行遍历，下面实现以右上角进行遍历，满足自上到下递增，自右到左递减，很显然像极了BST树的中序遍历。
class Solution {
public:
int m, n;
bool searchMatrix(vector<vector<int>>& matrix, int target) {
m = matrix.size(), n = matrix[0].size();
int i = 0, j = n - 1;
while (inMatrix(i, j)) {
if (matrix[i][j] == target) {
return true;
} else if (target < matrix[i][j]) {
j--;
} else if (target > matrix[i][j]) {
i++;
}
}
return false;
}
bool inMatrix(int x, int y) {
return x>=0 && x<m && y>=0 && y<n;
}
};
解法2：一次二分查找
根据矩阵自上到下，自左到右递增原则，每次执行后，我们可以锁定一部分区间，进行下一次选择，这不就是二分查找吗，将二维数组摊平为一维，再根据矩阵的规则进行二分。
class Solution {
public:
int m, n;
bool searchMatrix(vector<vector<int>>& matrix, int target) {
m = matrix.size(), n = matrix[0].size();
int l = 0, r = m*n-1;
while (l <= r) {
int mid = l + r >> 1;
int x = mid / n, y = mid % n;
if (matrix[x][y] == target) {
return true;
} else if (target < matrix[x][y]) {
r = mid - 1;
} else if (target > matrix[x][y]) {
l = mid + 1;
}
}
return false;
}
};
解法3：使用库函数两次二分查找
这里采用lower_bound与upper_bound进行查找，第一次锁定行，第二次根据行锁定目标元素。
upper_bound锁定行：upper_bound是查找第一个大于target的数，那么-1就是我们想要的小于等于的数，便锁定了行。lowwer_bound锁定目标值，根据上面得到的行，在当前行进行二分查找目标值。找到第一个大于等于target的值。最后判断查找的值是否等于目标值，同时注意判断是否越界。
#include <algorithm>
class Solution {
public:
int m, n;
bool searchMatrix(vector<vector<int>>& matrix, int target) {
m = matrix.size(), n = matrix[0].size();
// if (m==1) {
// int y = lower_bound(matrix[0].begin(), matrix[0].end(),target) - matrix[0].begin();
// return y!=n && matrix[0][y] == target;
//}
vector<int> cols;
for (int i=0;i<m;i++) cols.push_back(matrix[i][0]);
int x = upper_bound(cols.begin(),cols.end(),target) - cols.begin() - 1;
// [[1]] 2 end
// [[1]] 1 end
// [[1]] 0
if (x < 0) return false;
int y = lower_bound(matrix[x].begin(), matrix[x].end(),target) - matrix[x].begin();
return y!=n && matrix[x][y] == target;
}
};
解法4：自己编写实现两次二分查找
思路同解法3，就不赘述了。
#include <algorithm>
class Solution {
public:
int m, n;
bool searchMatrix(vector<vector<int>>& matrix, int target) {
m = matrix.size(), n = matrix[0].size();
// 查找第一个小于等于target的数
int l = 0, r = m - 1;
// [l,r) -> [l,mid-1) [mid,r)
while (l < r) {
int mid = l + r + 1 >> 1;
if (matrix[mid][0]<=target) l = mid;
else r = mid - 1;
}
// 此时l表示待查询的行
// 查询第一个大于等于target的数
int ll = 0, rr = n - 1;
// [ll,rr) -> [ll,mid) [mid+1,rr)
while (ll < rr) {
int mid = ll + rr >> 1;
if (matrix[l][mid] >= target) rr = mid;
else ll = mid + 1;
}
return matrix[l][ll] == target;
}
};
本节完~
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-03-30，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
