LeetCode刷题实战74：搜索二维矩阵-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 搜索二维矩阵，我们先来看题面：

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

Write an efficient algorithm that searches for a value in an m x n 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.

题意

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

每行中的整数从左到右按升序排列。

每行的第一个整数大于前一行的最后一个整数。

样例

解题

https://www.cnblogs.com/techflow/p/13042496.html

这题刚拿到手可能会有些蒙，我们当然很容易可以看出来这是一个二分的问题，但是我们之前做的二分都是在一个一维的数组上，现在的数据是二维的，我们怎么二分呢？

我们仔细阅读一下题意，再观察一下样例，很容易发现，如果一个二维数组满足每一行和每一列都有序，并且保证每一行的第一个元素大于上一行的最后一个元素，那么如果我们把这个二维数组reshape到一维，它依然是有序的。

比如说有这样一个二维数组：

[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]

它reshape成一维之后会变成这样：[1, 2, 3, 4, 5, 6, 7, 8, 9]

reshape是numpy当中的说法，也可以简单理解成把每一行串在一起。所以这题最简单的做法就是把矩阵降维，变成一位的数组之后再通过二分法来判断元素是否存在。如果偷懒的话可以用numpy来reshape，如果不会numpy的话，可以看下我之前关于numpy的教程，也可以自己用循环来处理。

reshape之后就是简单的二分了，完全没有任何难度：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        import numpy as np
        arr = np.array(matrix)
        # 通过numpy可以直接reshape
        arr = arr.reshape((-1, ))
        l, r = 0, arr.shape[0]
        if r == 0:
            return False
        # 套用二分
        while l+1 < r:
            m = (l + r) >> 1
            if arr[m] <= target:
                l = m
            else:
                r = m
        return arr[l] == target

正经做法

引入numpy reshape只是给大家提供一个解决的思路，这显然不是一个很好的做法。那正确的方法应该是怎样的呢？

还是需要我们对问题进行深入分析，正向思考感觉好像没什么头绪，我们可以反向思考。这也是解题常用的套路，假设我们已经知道了target这个数字存在矩阵当中，并且它的行号是i，列号是j。那么根据题目当中的条件，我们能够得出什么结论呢？

我们分析一下元素的大小关系，可以得出行号小于i的所有元素都小于它，行号大于i的所有元素都大于它。同行的元素列号小于j的元素小于它，列号大于j的元素大于它。

也就是说，行号i就是一条隐形的分界线，将matrix分成了两个部分，i上面的小于target，i下方的大于target。所以我们能不能通过二分找到这个i呢？

想到这里就很简单了，我们可以通过每行的最后一个元素来找到i。对于一个二维数组而言，每行的最后一个元素连起来就是一个一维的数组，就可以很简单地进行二分了。

找到了行号i之后，我们再如法炮制，在i行当中进行二分来查找j的位置。找到了之后，再判断matrix[i][j]是否等于target，如果相等，那么说明元素在矩阵当中。

整个的思路应该很好理解，但是实现的时候有一个小小的问题，就是我们查找行的时候，找的是大于等于target的第一行的位置。也就是说我们查找的是右端点，那么二分的时候维护的是一个左开右闭的区间。在边界的处理上和平常使用的左闭右开的写法相反，注意了这点，就可以很顺利地实现算法了：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n = len(matrix)
        if n == 0:
            return False
        
        m = len(matrix[0])
        if m == 0:
            return False
        
        # 初始化，左开右闭，所以设置成-1， n-1
        l, r = -1, n-1
        
        while l+1 < r:
            mid = (l + r) >> 1
            # 小于target的时候移动左边界
            if matrix[mid][m-1] < target:
                l = mid
            else:
                r = mid
                
        row = r
        
        # 正常的左闭右开的二分
        l, r = 0, m
        
        while l+1 < r:
            mid = (l + r) >> 1
            if matrix[row][mid] <= target:
                l = mid
            else:
                r = mid
                
        return matrix[row][l] == target

我们用了两次二分，查找到了结果，每一次二分都是一个O(logN)的算法，所以整体也是log级的算法。

优化

上面的算法没有问题，但是我们进行了两次二分，感觉有些麻烦，能不能减少一次，只使用一次二分呢？

如果想要只使用一次二分就找到答案，也就是说我们能找到某个方法来切分整个数组，并且切分出来的数组也存在大小关系。这个条件是使用二分的基础，必须要满足。

我们很容易在数组当中找到这样的切分属性，就是元素的位置。在矩阵元素的问题当中，我们经常用到的一种方法就是对矩阵当中的元素进行编号。比如说一个点处于i行j列，那么它的编号就是i * m + j，这里的m是每行的元素个数。这个编号其实就是将二维数组压缩到一维之后元素的下标。

我们可以直接对这个编号进行二分，编号的取值范围是确定的，是[0, mn)。我们有了编号之后，可以还原出它的行号和列号。而且根据题目中的信息，我们可以确定这个矩阵当中的元素按照编号也存在递增顺序。所以我们可以大胆地使用二分了：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n = len(matrix)
        if n == 0:
            return False
        
        m = len(matrix[0])
        if m == 0:
            return False
        
        l, r = 0, m*n
        
        while l+1 < r:
            mid = (l + r) >> 1
            # 还原行号和列号
            x, y = mid // m, mid % m
            if matrix[x][y] <= target:
                l = mid
            else:
                r = mid
        return matrix[l // m][l % m] == target