题目链接：剑指 Offer 04. 二维数组中的查找

解题思路：根据矩阵特点查找目标元素

示例矩阵：

  1. [
  2.   [1,   4,  7, 11, 15],
  3.   [2,   5,  8, 12, 19],
  4.   [3,   6,  9, 16, 22],
  5.   [10, 13, 14, 17, 24],
  6.   [18, 21, 23, 26, 30]
  7. ]

矩阵满足每一行按照从左到右递增，每一列按照从上到下递减的顺序排列。

对于这种有规律的数据结构，我们都需要观察数据结构的特点，从而求解。

算法思路：

从矩阵的 右上角 或 左下角 出发

  • 如果从矩阵右上角出发，矩阵当前位置的数字与 target 进行比较，如果 target 更大，那么说明 target 在当前矩阵索引的那个数的下面；如果更小，说明 target 在当前矩阵索引的那个数的左边
  • 如果从矩阵左下角出发，矩阵当前位置的数字与 target 进行比较，如果 target 更大，那么说明 target 在当前矩阵索引的那个数的右边；如果更小 ，说明 target 在当前矩阵索引的那个数的上面

代码

Java

  1. class Solution {
  2.     public boolean findNumberIn2DArray(int[][] matrix, int target) {
  3.         if(matrix.length == 0 || matrix[0].length == 0){
  4.             return false;
  5.         }
  6.         int row = 0;
  7.         int col = matrix[0].length - 1;
  8.         while(row <= matrix.length - 1 && col >= 0){
  9.             if(matrix[row][col] == target){
  10.                 return true;
  11.             }
  12.             if(matrix[row][col] < target){
  13.                 row++;
  14.             }else {
  15.                 col--;
  16.             }
  17.         }
  18.         return false;
  19.     }
  20. }

复杂度分析

  • 时间复杂度：O(M + N)
    其中，M 与 N 分别代表矩阵的行数与列数，我们的算法最多走完一行与一列即可得出结论，所以时间复杂度为：O(M + N)
  • 空间复杂度：O(1)
    整个算法只使用到了 row 和 col 两个额外变量，所以该算法的额外空间复杂度为：O(1)