使用 JavaScript 解答 LeetCode 第 240 题，搜索二维矩阵II，中等难度。

题目

原题链接

本题目是 LeetCode 题库第 240 题，由此访问。

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例:现有矩阵 matrix 如下：

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

给定 target = 5，返回 true。

给定 target = 20，返回 false。

解题

AC 样例

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    if(matrix.length == 0) return false;
    const n = matrix[0].length-1;
    return helper(matrix, 0, n, target);
};

const helper = (matrix, y, x, target) => {
    if(x < 0 || y > matrix.length-1) return false;
    if(matrix[y][x] == target) return true;
    if(matrix[y][x] > target) return helper(matrix, y, x-1, target);
    if(matrix[y][x] < target) return helper(matrix, y+1, x, target);
}

解题思路

根据题目要求，矩阵内每一点的右侧、下侧数字均大于其自身的数字，每一点的左侧、上侧数字均小于其自身数字。参考这一规律，选定矩阵左下角或右上角开始进行搜索。

本例从右上角开始搜索，可以将矩阵作为一个二叉搜索树处理。当被搜索到的数据小于目标数据时，向下搜索（右子树）；当被搜索到的数据大于目标数据时，向左搜索（左子树）。重复上述操作，直至当被搜索到的数据为目标数据时（搜索命中），返回 true 值，否则应搜索至超出矩阵边界为止。