难度: Medium
给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。
示例:
现有矩阵 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。
给定 target = 20，返回 false。
Submission
运行时间: 26 ms
内存: 20.4 MB
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if len(matrix)==0 or len(matrix[0])==0:
return False
hs=len(matrix)
rs=len(matrix[0])
for i in range(hs):
if target<=matrix[i][rs-1]:
for j in range(rs):
if target==matrix[i][j]:
return True
return False
Explain
该题解采用的是逐行扫描的方法。首先，检查矩阵是否为空。对于每一行，如果该行的最后一个元素大于或等于目标值，则在该行中逐个检查元素是否等于目标值。这种方法是基于每行和每列都是升序的事实，如果某行的最后一个元素已经小于目标值，那么目标值不可能出现在当前行或之前的行中。
时间复杂度: O(MN)
空间复杂度: O(1)
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if len(matrix)==0 or len(matrix[0])==0: # 检查矩阵是否为空
return False
hs=len(matrix) # 矩阵行数
rs=len(matrix[0]) # 矩阵列数
for i in range(hs): # 遍历每一行
if target<=matrix[i][rs-1]: # 检查目标值是否小于等于当前行的最后一个元素
for j in range(rs): # 在当前行中检查每个元素
if target==matrix[i][j]: # 如果找到目标值
return True
return False # 如果在所有行中都没有找到目标值
Explore
在给定的矩阵中，每一行和每一列都是升序排列的。如果在某一行的扫描过程中，我们检查了最后一个元素并发现它小于目标值，那么这意味着当前行及其之前的所有行都不可能包含目标值，因为这些行的所有元素都会小于或等于这一行的最后一个元素。反之，如果检查第一个元素，无论其值如何，都无法提供类似的有用信息，因为即使第一个元素大于目标值，目标值仍可能出现在行中的其他位置。因此，检查每行的最后一个元素是一种更有效的筛选方式，可以快速确定目标值是否可能存在于该行。
如果矩阵的行数远大于列数，逐行扫描然后在行内逐元素检查的效率可能会较低，因为即使使用行的最后一个元素进行初步过滤，仍需对许多行进行完整扫描。同理，如果列数远大于行数，问题同样存在。在这种情况下，更优的搜索方法是使用类似于二分搜索的方法，称为分步搜索（也被称为'从右上角开始'或'从左下角开始'的搜索方法）。这种方法在每一步中都利用矩阵的行和列的有序性来排除行或列，从而更快地缩小搜索范围，提高效率。
该检查是为了处理矩阵为空或矩阵中某些行为空的情况。这是边界情况处理，确保在执行任何进一步操作之前，输入的矩阵是有效的。例如，如果输入的矩阵是`[]`（即没有行的矩阵），或者是`[[]]`（即有一行但该行没有元素），这两种情况下，矩阵都不包含任何元素，因此无论目标值是什么，搜索结果应该是`False`。此检查确保程序在尝试访问元素之前不会因为这些无效的输入而出现错误。