LeetCode 74 BAT经典面试题，在矩阵上做二分
LeetCode 74 BAT经典面试题，在矩阵上做二分
今天是LeetCode专题43篇文章，我们今天来看一下LeetCode当中的74题，搜索二维矩阵，search 2D Matrix。
这题的官方难度是Medium，通过率是36%，和之前的题目不同，这题的点赞比非常高，1604个赞，154个反对。可见这题的质量还是很高的，事实上也的确如此，我就曾经在BAT的面试当中见过这道题。
题意
这题的题意也很简单，给定一个二维的数组matrix和一个整数target，这个数组当中的每一行和每一列都是递增的，并且还满足每一行的第一个元素大于上一行的最后一个元素。要求我们返回一个bool变量，代表这个target是否在数组当中。
也就是说这个是一个典型的判断元素存在的问题，我们下面来看看两个样例：
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: trueInput:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false题解
这题刚拿到手可能会有些蒙，我们当然很容易可以看出来这是一个二分的问题，但是我们之前做的二分都是在一个一维的数组上，现在的数据是二维的，我们怎么二分呢？
我们仔细阅读一下题意，再观察一下样例，很容易发现，如果一个二维数组满足每一行和每一列都有序，并且保证每一行的第一个元素大于上一行的最后一个元素，那么如果我们把这个二维数组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这样一来我们的代码大大简化，并且代码运行的效率也提升了，要比使用两次二分的方法更快。
总结
这道题到这里就结束了，这题难度并不大，想出答案来还是不难的。但是如果在面试当中碰到，想要第一时间想到最优解法还是不太容易。这一方面需要我们积累经验，看到题目大概有一个猜测应该使用什么类型的算法，另一方面也需要我们对问题有足够的理解和分析，从而读到题目当中的隐藏信息。
关于这题还有一个变种，就是去掉其中每行的第一个元素大于上一行最后一个元素的限制。那么矩阵当中元素按照编号顺序递增的性质就不存在了，对于这样的情况， 我们该怎么样运用二分呢？这个问题是LeetCode的240题，感兴趣的话可以去试着做一下这题，看看究竟解法有多大的变化。