题目:
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
试例 1:
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
试例 2:
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
主要思路: 读懂题意后需要明确 1. 开始寻找的位置, 2. 当遍历到的数比目标数字大时, 该如何移动? 3. 当遍历到的数比目标数字小时, 该如何移动?
故此题开始寻找的位置最好是左下角或者是右上角, 为何这样说呢? 此处拿右上角为开始寻找的位置来说吧, 当遍历到的数字比寻找的目标数字大时, 我们可以往右继续去寻找数字; 若遍历到的数字比寻找的目标数字小时, 我们可以往下继续寻找数字。
class Solution {
public:
bool findNumberIn2DArray(vector>& matrix, int target) {
if(matrix.size() == 0) return false; // 若二维数组为空
int row = matrix.size(); // 获取二维数组的行数
int col = matrix[0].size(); // 获取二维数组的列数
int i = 0, j = col-1;
while(i=0) // 防止越界
{
if(matrix[i][j]>target) j--;
else if(matrix[i][j] < target) i++;
else if(matrix[i][j] == target) return true;
}
return false;
}
};
欢迎大家前来观看, 如果有更好的思路或想法, 欢迎各位在下方评论区留言噢, 谢谢大家~
