难度

简单

思路

暴力遍历

  • 从左至右，从上往下挨个遍历即可。

    1. public static boolean findNumberIn2DArray_1(int[][] matrix, int target) {
    2.   // 做任何题之前都需要判断边界条件
    3.   if (matrix == null || matrix.length == 0)
    4.       return false;
    5.   int columnLength = matrix[0].length;
    6.   int lineLength = matrix.length;
    8.   for (int i = 0; i < columnLength; i++) {
    9.       for (int j = 0; j < lineLength; j++) {
    10.           if (matrix[j][i] == target) {
    11.               return true;
    12.           }
    13.       }
    14.   }
    15.   return false;
    16. }

    | 时间复杂度 | O(m*n) | | —- | —- | | 空间复杂度 | O(1) |

二叉查找法

  • 从右上角观察，可把矩阵看成一棵二叉树，可用遍历、递归求解。

    1. public static boolean findNumberIn2DArray_3(int[][] matrix, int target) {
    2.   if (matrix == null || matrix.length == 0 || matrix[0].length < 1) {
    3.       return false;
    4.   }
    6.   // 从右上角遍历
    7.   int line = matrix.length - 1;       // 行值
    8.   int column = matrix[0].length - 1;  // 列值
    9.   int i = 0, j = column; // 指针
    11.   // 需要保证两个指针不能越界
    12.   while (j >= 0 && i <= line) {
    13.       // 如果目标值大于当前矩阵值，则下移
    14.       if (matrix[i][j] < target) {
    15.           i++;
    16.       } else if (matrix[i][j] == target) {
    17.           return true;
    18.       } else {
    19.           // 如果目标值小于当前矩阵值，则左移
    20.           j--;
    21.       }
    22.   }
    23.   return false;
    24. }

    | 时间复杂度 | O(m+n) | | —- | —- | | 空间复杂度 | O(1) |

总结

  • 切记不能忘记边界条件判断
  • 切记不能忘记初始值条件判断
  • 二叉查找思路比较简单清晰，
    • 从右上角开始查找，如果 当前值＞目标值，则列值--，如果当前值＜目标值，则行值++
    • 遇到现值相等，就是遇到对的人，直接返回 true 即可。
  • 对于二级数组（matrix），有:
    • 行值: **_i=matrix.length_**
    • 列值: **_j=matrix[0].length_**
    • 左移 i++，下移 j++