(Leetcode 2021 刷题计划) 74. 搜索二维矩阵
原创
每日一题时间:
2020-03-30题目链接: 74. 搜索二维矩阵 官方题解链接: 搜索二维矩阵
题目
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
解题方法
遍历
解题思路: 利用矩阵特性, 从左下角进行遍历, 保证单调, 如果大于目标值则向上移动, 如果小于目标值则向右移动。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int row = m - 1, col = 0;
while (row >= 0 && col < n) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
--row;
} else {
++col;
}
}
return false;
}
};- 复杂度分析
- 时间复杂度:
O(N)(最差场景:N x 1) - 空间复杂度:
O(1)
- 时间复杂度:
二分搜索
解题思路: 本题较为特殊, 相较于仅有行单调性，该题还存在下一行行首大于上一行行尾的限制, 因此可以采用二分查找的方式。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int left = 0, right = m * n - 1, mid, cur;
while (left <= right) {
mid = left + (right - left) / 2;
cur = matrix[mid / n][mid % n];
if (cur == target) {
return true;
} else if (cur > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return false;
}
};- 复杂度分析
- 时间复杂度:
O(log m x n) - 空间复杂度:
O(1)
- 时间复杂度:
参考资料
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录