74. 搜索二维矩阵

https://leetcode-cn.com/problems/search-a-2d-matrix

• 74. 搜索二维矩阵

  • 题目描述

  • 方法 1：二分法

    • 思路

    • 复杂度分析

    • 代码

题目描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。


示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
输出：true
示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
输出：false
示例 3：

输入：matrix = [], target = 0
输出：false


提示：

m == matrix.length
n == matrix[i].length
0 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1：二分法

思路

如果我们能把二维数组打平成一维数组，那就是套个二分法模板的事啦。

剩下的问题是，怎么从一维数组的下标逆推二维数组的坐标？其实就是简单的数学计算。

我们将二维数组中的数字从左到右、从上到下，标记为第 0~(m x n) 个数字，用 pos 来表示。那么 pos 与数字在二维矩阵中坐标的关系如下：

x: floor(pos / cols)
y: pos % cols

• pos: 第 n 个数字

• cols: 二维矩阵的列数

复杂度分析

• 时间复杂度：$O(log(mn))$，$m n$ 是矩阵的大小。

• 空间复杂度：$O(1)$。

代码

JavaScript Code

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    if (!matrix || !matrix.length) return false;

    const rows = matrix.length;
    const cols = matrix[0].length;
    let l = 0,
        r = rows * cols - 1,
        mid = 0;

    while (l <= r) {
        mid = ((l + r) / 2) << 0;
        const [x, y] = getCoordFromPos(mid);
        const num = matrix[x][y];
        if (num < target) l = mid + 1;
        else if (num > target) r = mid - 1;
        else return true;
    }

    return false;

    // *************************************
    function getCoordFromPos(pos) {
        const x = (pos / cols) << 0;
        const y = pos % cols;
        return [x, y];
    }
};