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

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

暴力搜索

var findNumberIn2DArray = function(matrix, target) {
    let rowLen = matrix.length;
    if (rowLen === 0) return false;
    let colLen = matrix[0].length;
      // 遍历每一行
    for (let i = 0; i < rowLen; i++) {
          // 如果 target 在当前行，才会遍历当前行
        if (target >= matrix[i][0] && target <= matrix[i][colLen - 1]) {
            for (let j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] === target) return true;
            }
        }
    }
    return false;
};

把矩阵逆时针旋转 45°

发现其结构类似 二分搜索树

图片转自 https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vl81e/

public boolean findNumberIn2DArray(int[][] matrix, int target) {
    // 总行数
    int rowCount = matrix.length;
    // 如果总行数为 0
    if (rowCount == 0) return false;
    // 总列数
    int colCount = matrix[0].length;
    // 定义顶点坐标，在右上角
    int i = 0;
    int j = colCount - 1;
    // 如果没有越界，因为 i 只会递增，j 只会递减，所以只需要判断一边
    while (i < rowCount && j >= 0) {
        // 为了方便对比，用临时变量存储当前节点值
        int temp = matrix[i][j];
        // 如果匹配了，返回 true
        if (temp == target) return true;
        // 往树的右边移动
        else if (temp < target) i ++;
        // 往树的左边移动
        else j --;
    }
    return false;
}