剑指 Offer 04. 二维数组中的查找

思路

(1) 暴力法：遍历整个二维数组，时间复杂度为O(n*m)

(2) 二分查找：对每一行进行二分查找，时间复杂度为O(n*logm)，但这样没有用到"每一列都按照从上到下递增的顺序排序"这个条件

(3) 将矩阵旋转45度，讲解如下：

代码实现

 1 class Solution {
 2 public:
 3     bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
 4         //n行m列
 5         int n = matrix.size();
 6         if(n == 0)
 7             return false;
 8         int m = matrix[0].size();
 9         if(m == 0)
10             return false;
11 
12         //从右上角元素开始搜索(左下角开始也行)
13         int i = 0, j = m-1;
14         while(1) {
15             if(matrix[i][j] == target) {
16                 return true;
17             } else if (matrix[i][j] < target) {
18                 ++i; //消去第i行
19                 if(i >= n) 
20                     break;
21             } else {
22                 --j; //消去第j列
23                 if(j < 0) 
24                     break;
25             }
26         }
27         return false;
28     }
29 };

复杂度分析

参考

面试题04. 二维数组中的查找（标志数，清晰图解）