力扣hot100 ——搜刮二维矩阵 || m+n复杂度优化解法
编写一个高效的算法来搜刮 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：[*]每行的元素从左到右升序分列。
[*]每列的元素从上到下升序分列。
解题思路：
借助行和列有序特性，不断按行或者列缩小范围；途中数字表现每次执行，不同颜色框出的范围就是每次缩小后的区域，由于不是按行就是按列缩小，以是时间复杂度就是O（m+n）
https://i-blog.csdnimg.cn/direct/af06bf21b507401ebd5eab778deda5d5.png
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
// 边界缩小查找
// 从右上角开始缩小；先水平调整，然后竖直缩小
// 借助行和列有序特性，不断按行或者列缩小范围；由于不是按行就是按列缩小，所以时间复杂度就是O（m+n）
int rows = matrix.size(),clos = matrix.size(); // row 行上限clo 列上限
int row = 0,clo = clos - 1;
if(target > matrix){
return false;
}
while(row < rows && clo >= 0){
if(matrix == target){
return true;
}
else if(matrix > target){
--clo;
}
else{
++row;
}
}
return false;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]