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

参考资料