每日一题时间:
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.length
n == matrix[i].length
1 <= 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 删除。