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;
};

參考資料