74. Search a 2D Matrix

Leetcode 問題: 74. Search a 2D Matrix
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 from left to right.

The first integer of each row is greater than the last integer of the previous row.

傳入一個二維矩陣 matrix，試著搜尋想要的數字 target是否在矩陣中，如果有回傳 true，如果沒有回傳 false

矩陣格式條件

  • 每個 單列（row）的數字 由左到右 都是 由小到大正向排序
  • 每個 單列（row）的數字都比上一個單列（row）的數字還要大

Example

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

74. Search a 2D Matrix

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

74. Search a 2D Matrix

演算法 1

1. 把整個二維矩陣扁平化成一個一為陣列

因為矩陣格式條件

  • 每個 單列（row）的數字 由左到右 都是 由小到大正向排序
  • 每個 單列（row）的數字都比上一個單列（row）的數字還要大

所以其實從左到右，然後從上到下都是一個由小到大正向排序的陣列

可以對整個二維陣列直接進行二元搜尋

只需要計算每個中間指標所在的 列 row 與 欄 column 把資料取出來做比較計算即可

矩陣計算 公式
指標在哪一列 row 指標位置 / 矩陣欄數 (無條件捨去)
指標在哪一欄 column 指標位置 % 矩陣欄數 (無條件捨去)

演算法 1 答案

JavaScript

function searchMatrix(numberMatrix, searchNumberTarget) {
    // 矩陣「列 row」的數量
    var numberMatrixRowsCount = numberMatrix.length;
    // 矩陣「欄 column」的數量
    var numberMatrixColumnCount = numberMatrix[0].length;
    // 左指標，第一個數字
    var leftPointer = 0;
    // 右指標，整個矩陣數量
    var rightPointer = numberMatrixRowsCount * numberMatrixColumnCount - 1;
    while (leftPointer <= rightPointer) {
        // 中間指標
        var middlePointer = Math.floor((rightPointer + leftPointer) / 2);
        // 中間指標在哪一列 row
        var middlePointerRow = Math.floor(middlePointer / numberMatrixColumnCount);
        // 中間指標在哪一欄 column
        var middlePointerColumn = Math.floor(middlePointer % numberMatrixColumnCount);
        // 中間指標數字
        var middleNumber = numberMatrix[middlePointerRow][middlePointerColumn];
        if (searchNumberTarget == middleNumber) {
            // 找到指定數字了，跳離開迴圈
            return true;
        }
        else if (searchNumberTarget < middleNumber) {
            // 如果「要搜尋的數字」小於「中間指標的數字」，表示數字在「中間指標」上方
            // 將「下方指標」設定為「目前中間指標位置 - 1」
            rightPointer = middlePointer - 1;
        }
        else {
            // 如果「要搜尋的數字」大於「中間指標的數字」，表示數字在「中間指標」下方
            // 將「上方指標」設定為「目前中間指標位置 + 1」
            leftPointer = middlePointer + 1;
        }
    }
    // 都沒有找到
    return false;
}

TypeScript

function searchMatrix(numberMatrix: number[][], searchNumberTarget: number): boolean {
    // 矩陣「列 row」的數量
    let numberMatrixRowsCount = numberMatrix.length;
    // 矩陣「欄 column」的數量
    let numberMatrixColumnCount = numberMatrix[0].length;

    // 左指標，第一個數字
    let leftPointer = 0;
    // 右指標，整個矩陣數量
    let rightPointer = numberMatrixRowsCount * numberMatrixColumnCount -1;

    while (leftPointer <= rightPointer) {
        // 中間指標
        let middlePointer = Math.floor((rightPointer + leftPointer) / 2);
        // 中間指標在哪一列 row
        let middlePointerRow = Math.floor(middlePointer / numberMatrixColumnCount);
        // 中間指標在哪一欄 column
        let middlePointerColumn = Math.floor(middlePointer % numberMatrixColumnCount);
        // 中間指標數字
        let middleNumber = numberMatrix[middlePointerRow][middlePointerColumn];

        if (searchNumberTarget == middleNumber) {
            // 找到指定數字了，跳離開迴圈
            return true;
        } else if (searchNumberTarget < middleNumber) {
            // 如果「要搜尋的數字」小於「中間指標的數字」，表示數字在「中間指標」上方
            // 將「下方指標」設定為「目前中間指標位置 - 1」
            rightPointer = middlePointer - 1;
        } else {
            // 如果「要搜尋的數字」大於「中間指標的數字」，表示數字在「中間指標」下方
            // 將「上方指標」設定為「目前中間指標位置 + 1」
            leftPointer = middlePointer + 1;
        }
    }

    // 都沒有找到
    return false;
};

演算法 2

1. 二元搜尋找最接近答案的那一「列 row」

因為答案可能出現在任何地方，如果全部的「列 row」都搜尋，當資料量較大會比較慢一點

因為「每一列 row」的第一個數字都是比「前一列 row」的所有數字都大

所以可以先比較「每一列 row」的第一個數字，找尋最接近答案的那一列的第一個數字，但那一列的第一個數字不能大於要找的答案

那就可以把答案範圍限縮在最可能輸線的那一列

2. 二元搜尋找出來的「列 row」 所有數字

上一個二元搜尋，已經排除了所有不可能的「列 row」，最後一個剩下的列，就是最有可能出現答案的「列 row」

所以只需要針對剩下的列做第 2 次二元搜尋，就可以直接找到答案

演算法 2 答案

JavaScript

function searchMatrix(numberMatrix, searchNumberTarget) {
    // 矩陣「列 row」的數量
    var numberMatrixRowsCount = numberMatrix.length;
    // 矩陣「欄 column」的數量
    var numberMatrixColumnCount = numberMatrix[0].length;
    // 上下搜尋，確認數字在「哪一列 row」
    // 上方指標
    var topRowMatrixPointer = 0;
    // 下方指標（矩陣總共有多少列 - 1）
    var bottomRowMatrixPointer = numberMatrixRowsCount - 1;
    // console.log(searchNumberTarget);
    while (topRowMatrixPointer <= bottomRowMatrixPointer) {
        // 中間指標
        var middleRowMatrixPointer = topRowMatrixPointer + Math.floor((bottomRowMatrixPointer - topRowMatrixPointer) / 2);
        // 取得中間指標的數字
        var middleRowNumber = numberMatrix[middleRowMatrixPointer][0];
        if (searchNumberTarget == middleRowNumber) {
            // 找到指定數字了，跳離開迴圈
            return true;
        }
        else if (searchNumberTarget < middleRowNumber) {
            // 如果「要搜尋的數字」小於「中間指標的數字」，表示數字在「中間指標」上方
            // 將「下方指標」設定為「目前中間指標位置 - 1」
            bottomRowMatrixPointer = middleRowMatrixPointer - 1;
        }
        else {
            // 如果「要搜尋的數字」大於「中間指標的數字」，表示數字在「中間指標」下方
            // 將「上方指標」設定為「目前中間指標位置 + 1」
            topRowMatrixPointer = middleRowMatrixPointer + 1;
        }
    }
    // 「上方指標」會超過「要搜尋的數字」，所以「上方指標」的「上一欄 row」是要搜尋的數字可能在的「欄 row」
    // 設定搜尋的欄 row
    var searchRow = topRowMatrixPointer - 1;
    if (searchRow < 0) {
        // 數字比最上層還小，不用找了
        return false;
    }
    // 左方指標
    var searchRowLeftColumnPointer = 0;
    // 右方指標（矩陣總共有多少欄 - 1）
    var searchRowRightColumnPointer = numberMatrixColumnCount - 1;
    while (searchRowLeftColumnPointer <= searchRowRightColumnPointer) {
        // 中間指標
        var middleColumnPointer = searchRowLeftColumnPointer + Math.floor((searchRowRightColumnPointer - searchRowLeftColumnPointer) / 2);
        // 取得中間指標的數字
        var middleColumnNumber = numberMatrix[searchRow][middleColumnPointer];
        if (searchNumberTarget == middleColumnNumber) {
            // 找到指定數字了，跳離開迴圈
            return true;
        }
        else if (searchNumberTarget < middleColumnNumber) {
            // 如果「要搜尋的數字」小於「中間指標的數字」，表示數字在「中間指標」左方
            // 將「右方指標」設定為「目前中間指標位置 - 1」
            searchRowRightColumnPointer = middleColumnPointer - 1;
        }
        else if (searchNumberTarget > middleColumnNumber) {
            // 如果「要搜尋的數字」大於「中間指標的數字」，表示數字在「中間指標」右方
            // 將「左方指標」設定為「目前中間指標位置 + 1」
            searchRowLeftColumnPointer = middleColumnPointer + 1;
        }
    }
    // 都沒有找到
    return false;
}

TypeScript

function searchMatrix(numberMatrix: number[][], searchNumberTarget: number): boolean {
    // 矩陣「列 row」的數量
    let numberMatrixRowsCount = numberMatrix.length;
    // 矩陣「欄 column」的數量
    let numberMatrixColumnCount = numberMatrix[0].length;

    // 上下搜尋，確認數字在「哪一列 row」
    // 上方指標
    let topRowMatrixPointer :number = 0;
    // 下方指標（矩陣總共有多少列 - 1）
    let bottomRowMatrixPointer :number = numberMatrixRowsCount - 1;

    // console.log(searchNumberTarget);
    while (topRowMatrixPointer <= bottomRowMatrixPointer) {
        // 中間指標
        let middleRowMatrixPointer = topRowMatrixPointer + Math.floor((bottomRowMatrixPointer - topRowMatrixPointer) / 2);
        // 取得中間指標的數字
        let middleRowNumber = numberMatrix[middleRowMatrixPointer][0];

        if (searchNumberTarget == middleRowNumber) {
            // 找到指定數字了，跳離開迴圈
            return true;
        } else if (searchNumberTarget < middleRowNumber) {
            // 如果「要搜尋的數字」小於「中間指標的數字」，表示數字在「中間指標」上方
            // 將「下方指標」設定為「目前中間指標位置 - 1」
            bottomRowMatrixPointer = middleRowMatrixPointer - 1;
        } else {
            // 如果「要搜尋的數字」大於「中間指標的數字」，表示數字在「中間指標」下方
            // 將「上方指標」設定為「目前中間指標位置 + 1」
            topRowMatrixPointer = middleRowMatrixPointer + 1;
        }
    }


    // 「上方指標」會超過「要搜尋的數字」，所以「上方指標」的「上一欄 row」是要搜尋的數字可能在的「欄 row」
    // 設定搜尋的欄 row
    let searchRow: number = topRowMatrixPointer - 1;
    if (searchRow < 0) {
        // 數字比最上層還小，不用找了
        return false;
    }

    // 左方指標
    let searchRowLeftColumnPointer = 0;
    // 右方指標（矩陣總共有多少欄 - 1）
    let searchRowRightColumnPointer = numberMatrixColumnCount - 1;

    while (searchRowLeftColumnPointer <= searchRowRightColumnPointer) {
        // 中間指標
        let middleColumnPointer = searchRowLeftColumnPointer + Math.floor((searchRowRightColumnPointer - searchRowLeftColumnPointer) / 2);
        // 取得中間指標的數字

        let middleColumnNumber = numberMatrix[searchRow][middleColumnPointer];

        if (searchNumberTarget == middleColumnNumber) {
            // 找到指定數字了，跳離開迴圈
            return true;
        } else if (searchNumberTarget < middleColumnNumber) {
            // 如果「要搜尋的數字」小於「中間指標的數字」，表示數字在「中間指標」左方
            // 將「右方指標」設定為「目前中間指標位置 - 1」
            searchRowRightColumnPointer = middleColumnPointer - 1;
        } else if (searchNumberTarget > middleColumnNumber) {
            // 如果「要搜尋的數字」大於「中間指標的數字」，表示數字在「中間指標」右方
            // 將「左方指標」設定為「目前中間指標位置 + 1」
            searchRowLeftColumnPointer = middleColumnPointer + 1;
        }
    }

    // 都沒有找到
    return false;
};

參考資料