【一刷《剑指Offer》】面试题 3：二维数组中的查找

 力扣对应题目链接：240. 搜索二维矩阵 II - 力扣（LeetCode）  

核心考点：数组相关，特性观察，时间复杂度把握。

---

一、《剑指Offer》对应内容

---

二、分析题目

1. 正常查找的过程本质就是排除的过程，谁排除的效率更高，谁对应查找的效率也就更高。
2. 如果双循环查找，本质是一次排除一个，效率过低。但采取从右上角 / 左下角进行比较，这样就可以一次排除一行或一列。
3. 注意临界条件。

---

三、代码（C++）

1、从右上角开始排查

//从右上角开始排查
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int i=0, j=matrix[0].size()-1;while(i<matrix.size() && j>=0){if(matrix[i][j]>target)j--;else if(matrix[i][j]<target)i++;else return true;}return false;}
};

注意：本题因为所提供数据范围为：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300

所以，排除了空数组的情况，否则还需要在开头进行特判。

例如，下面这道题目：LCR 121. 寻找目标值 - 二维数组 - 力扣（LeetCode）

//从右上角开始排查
class Solution {
public:bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {if(plants.size()==0 || plants[0].size()==0) return false;int i=0, j=plants[0].size()-1;while(i<plants.size() && j>=0){if(plants[i][j]>target)j--;else if(plants[i][j]<target)i++;else return true;}return false;}
};

注意：如果采用第二种方法：“从左下角开始排查”，则不需要进行特判，因为如果数组为空，第二种方法并不会进入到循环当中。

//从左下角开始排查
class Solution {
public:bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {int i=plants.size()-1, j=0;while(i>=0 && j<plants[0].size()){if(plants[i][j]>target)i--;else if(plants[i][j]<target)j++;else return true;}return false;}
};

---

2、从左下角开始排查

//从左下角开始排查
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int i=matrix.size()-1, j=0;while(i>=0 && j<matrix[0].size()){if(matrix[i][j]>target)i--;else if(matrix[i][j]<target)j++;else return true;}return false;}
};