每日一题：LeetCode-240. 搜索二维矩阵 II

作者：半亩房顶

2023-12-20
北京
本文字数：1290 字
阅读完需：约 4 分钟

刷题使我快乐，满脸开心.jpg

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

题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：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输出：true

复制代码

示例 2：

输入：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输出：false

复制代码

提示：

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109

思路

第一反应是二分法，但是看着题目中高效那两个字，总觉得很是扎眼，所以感觉对于一个矩阵来说，总归应该有些更高效的才对。

思路如下:

数据顺序是有两个方向的，横向和纵向，那么理论上我们是能够通过一个点来排除两个方向上的数据的，但是打个比方，发现[i][j]点的值比target小，我们能够排除比这个点左边和上边的所有数据，但是接下来我们是往右移动还是往左移动呢？感觉这个问题其实也比较复杂，那有没有没有歧义的移动方法呢？
然后就发现在这个矩阵中会有两个特殊的点，左下角和右下角，特殊之处在于，比这两个点大的方向和比这俩个点小的数据，都只有一个方向。这有一个方向，那么就没有歧义了，所以移动起来就只会有一种选择！

如图展示下寻找步骤：灰色部分为被淘汰的数据

如此，每次判断都可以 pass 掉一行或者一列数据，而在寻找过程中，当前点位也始终会保持在左下角或右下角这个特殊位置上

至此，上代码

代码

二分法

func searchMatrix(matrix [][]int, target int) bool {    for _, row := range matrix {        // 逐层搜索        if binarySearch(row, target) {            return true        }    }    return false}
// 二分法func binarySearch(nums []int, target int) bool {    n := len(nums)    if target > nums[n-1] || target < nums[0] {        return false    }    if target == nums[n-1] || target == nums[0] {        return true    }    left, right, mid := 0, n-1, 0    for left <= right {        mid = (left + right) / 2        if nums[mid] == target {            return true        } else if target > nums[mid] {            left = mid + 1        } else {            right = mid - 1        }    }    return false}

复制代码

z 字形查找（官解名）

func searchMatrix(matrix [][]int, target int) bool {    m := len(matrix)    n := len(matrix[0])    i, j := m-1, 0    for i >= 0 && j < n  {        if matrix[i][j] == target {            return true        } else if matrix[i][j] > target {            i--        } else {            j++        }    }    return false}

复制代码

欢迎关注公众号交流更多题目~

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/aa01fb5f79859b0452e362be0】。文章转载请联系作者。

半亩房顶

关注

人生那么长，能写多少bug？ 2018-11-16 加入

我希望，自己永远是自己。我希望，远离bug。

发布

暂无评论

创作场景

每日一题：LeetCode-240. 搜索二维矩阵 II

题目

思路

代码

二分法

z 字形查找（官解名）

半亩房顶

评论