搜索二维矩阵 II（LeetCode 240）

1.问题描述

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

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

示例：

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

2.难度等级

Medium。

3.热门指数

★★★★☆

4.解题思路

方法一：直接查找

我们直接遍历整个矩，判断 target 是否出现即可。

时间复杂度： O(mn)。

空间复杂度： O(1)。

下面以 Golang 为例给出实现。

func searchMatrix(matrix [][]int, target int) bool {
   
    for _, row := range matrix {
   
        for _, v := range row {
   
            if v == target {
   
                return true
            }
        }
    }
    return false
}

方法二：二分查找

由于矩阵中每一行的元素都是升序排列的，因此我们可以对每一行都二分查找，判断 targett 是否在该行中。

时间复杂度： O(mlogn)。对一行使用二分查找的时间复杂度为 O(log⁡n)，最多需要进行 m 次二分查找。

空间复杂度： O(1)。

下面以 Golang 为例给出实现。

func searchMatrix(matrix [][]int, target int) bool {
   
    for _, row := range matrix {
   
        i := sort.SearchInts(row, target)
        if i < len(row) && row[i] == target {
   
            return true
        }
    }
    return false
}

方法三：Z 字形查找

上面的两个方法效率并不高效，实际上还有线性时间复杂度的解法。

矩阵有两个特性：

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

那么我们可以比较明显得感知到这两个特性就会是我们解开这个题的关键所在了。

们以示例一的矩阵作为例子，如果我们以某一个边角作为出发点，那么我们会得出如下结论：

【左上角】从左到右，升序排列；从上到下，升序排列；
【右上角】从右到左，降序排列；从上到下，升序排列；
【左下角】从左到右，升序排列；从下到上，降序排列；
【右上角】从右到左，降序排列；从下到上，降序排列；

具体情况，请见下图所示：

通过上面我们的分析，可以发现左下角和右上角这两个出发点才是我们解题的关键，因为这两个点在水平方向移动和在垂直方向移动分别是递增或者递减的；那么我们就可以执行如下逻辑：

【如果当前格子的值 小于 target】那么就向递增方向移动；
【如果当前格子的值 大于 target】那么就向递减方向移动；
【如果当前格子的值 等于 target】那么返回 true；
【如果移动 越界 并且 不等于 target】那么返回 false；

下面以左下角为例，从左下角开始搜索 5。当然，从右上角搜索也是可以的。

时间复杂度： O(m+n)。最坏情况下是从右上角搜索到左下角，遍历了 m+n 个元素。

空间复杂度： O(1)。

下面以 Golang 为例给出实现。

func searchMatrix(matrix [][]int, target int) bool {
   
    m, n := len(matrix), len(matrix[0])

	// 从左下角开始搜索。
    x, y := m-1, 0
    for x >= 0 && y < n {
   
        if matrix[x][y] == target {
   
            return true
        }
        if matrix[x][y] > target {
   
            x--
        } else {
   
            y++
        }
    }
    return false
}

参考文献

240. 搜索二维矩阵II - LeetCode