240. Search a 2D Matrix II

Leetcode 问题: 240. Search a 2D Matrix II
Categories:
Tags:

题目

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.

Integers in each column are sorted in ascending from top to bottom.

传入一个二维矩阵 matrix，试着搜寻想要的数字 target是否在矩阵中，如果有回传 true，如果没有回传 false

矩阵格式条件

  • 每个 单列（row）的数字 由左到右 都是 由小到大正向排序
  • 每个 单栏 （column）的数字由上到下 都是 由小到大正向排序

Example

Input: 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
Output: true

240. Search a 2D Matrix II

Input: 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 = 20
Output: false

240. Search a 2D Matrix II

演算法

1. 由右到左搜寻，由上到下搜寻

从 第 0 列（row）及 最后一栏（column） 的数字开始比较

状况 A. 如果「要找的数字」等于「目前找到的数字」

直接找到要的数字，直接回传 true，后面不需要再找了

状况 B. 如果「要找的数字」比「目前找到的数字」还要小

因为每个 单栏 （column）的数字由上到下 都是 由小到大正向排序

所以 这一栏 （column） 的数字一定都是比「要找的数字」大，所以可以直接删去不用再看这一栏 （column） 的资料

所以「栏 column」指标往左移动

状况 C. 如果「要找的数字」比「目前找到的数字」还要大

因为每个 单列（row）的数字 由左到右 都是 由小到大正向排序

所以 这一列 （row） 的数字一定都是比「要找的数字」小，所以可以直接删去不用再看这一列 （row） 的资料

所以「列 row」指标往下移动

答案

JavaScript

function searchMatrix(numberMatrix, searchNumberTarget) {
    // 目标数字「列 row」指标
    var targetRowPointer = 0;
    // 目标数字「栏 column」指标
    var targetColumnPointer = numberMatrix[0].length - 1;
    // 由右到左搜寻（targetColumnPointer），由上到下搜寻（targetRowPointer）
    while (targetColumnPointer >= 0 && targetRowPointer < numberMatrix.length) {
        // 还有「栏 column」的资料，且还有「列 row」资料
        // 目前找到的数字
        var findNumber = numberMatrix[targetRowPointer][targetColumnPointer];
        if (findNumber == searchNumberTarget) {
            // 如果「目前找到的数字」与要求寻找的数字一样，表示找到了
            return true;
        }
        // 如果还没有找到数字
        if (findNumber > searchNumberTarget) {
            // 如果「目前找到的数字」比「要找的数字」还要大
            // 表示要「找的数字」在目前「栏 column」左边，所以「栏 column」往左移动
            targetColumnPointer--;
        }
        else {
            // 如果「目前找到的数字」比「要找的数字」还要小
            // 因为是由大找到小，所以表示现在的「这一列 row」的数字，都是小于「要找的数字」，所以直接跳过不用找
            targetRowPointer++;
        }
    }
    // 上面的矩阵都跑完了，都没有找到数字
    return false;
}

TypeScript

function searchMatrix(numberMatrix: number[][], searchNumberTarget: number): boolean {
    // 目标数字「列 row」指标
    let targetRowPointer = 0;
    // 目标数字「栏 column」指标
    let targetColumnPointer = numberMatrix[0].length - 1;

    // 由右到左搜寻（targetColumnPointer），由上到下搜寻（targetRowPointer）
    while (targetColumnPointer >=0 && targetRowPointer < numberMatrix.length) {
        // 还有「栏 column」的资料，且还有「列 row」资料
        // 目前找到的数字
        let findNumber = numberMatrix[targetRowPointer][targetColumnPointer];
        if (findNumber == searchNumberTarget) {
            // 如果「目前找到的数字」与要求寻找的数字一样，表示找到了
            return true;
        }

        // 如果还没有找到数字
        if (findNumber > searchNumberTarget) {
            // 如果「目前找到的数字」比「要找的数字」还要大
            // 表示要「找的数字」在目前「栏 column」左边，所以「栏 column」往左移动
            targetColumnPointer--;
        } else {
            // 如果「目前找到的数字」比「要找的数字」还要小
            // 因为是由大找到小，所以表示现在的「这一列 row」的数字，都是小于「要找的数字」，所以直接跳过不用找
            targetRowPointer++
        }
    }

    // 上面的矩阵都跑完了，都没有找到数字
    return false;
};

参考资料