如何建一个简单的网站,泰州市建设工程招标网,wordpress 宽屏主题,wordpress如何屏蔽特定国家的用户编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性#xff1a;
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
解题思路#xff1a;
借助行和列有序特性#xff0c;不断按行或者列缩小范围#xff1b;途中数字表示每…编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
解题思路
借助行和列有序特性不断按行或者列缩小范围途中数字表示每次执行不同颜色框出的范围就是每次缩小后的区域由于不是按行就是按列缩小所以时间复杂度就是Omn class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {// 边界缩小查找// 从右上角开始缩小先水平调整然后竖直缩小// 借助行和列有序特性不断按行或者列缩小范围由于不是按行就是按列缩小所以时间复杂度就是Omnint rows matrix.size(),clos matrix[0].size(); // row 行上限 clo 列上限int row 0,clo clos - 1;if(target matrix[rows-1][clos - 1]){return false;}while(row rows clo 0){if(matrix[row][clo] target){return true;}else if(matrix[row][clo] target){--clo;}else{row;}}return false;}
};
