题目
240. 搜索二维矩阵 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
我的代码（Python）
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or not matrix[0]:
return False
if target < matrix[0][0] or target > matrix[-1][-1]:
return False
m = len(matrix)
n = len(matrix[0])
beg_r, end_r = 0, m - 1
r = -1
while beg_r <= end_r:
cen_r = (beg_r + end_r) // 2
if matrix[cen_r][0] > target:
end_r = cen_r - 1
elif matrix[cen_r][-1] < target:
beg_r = cen_r + 1
else:
end_r = cen_r
if beg_r == end_r:
r = beg_r
break
if r == -1:
return False
for row in range(r, m):
if matrix[row][0] > target:
break
beg_c, end_c = 0, n - 1
while beg_c <= end_c:
cen_c = (beg_c + end_c) // 2
if matrix[row][cen_c] == target:
return True
if beg_c == end_c:
break
if matrix[row][cen_c] < target:
beg_c = cen_c + 1
else:
end_c = cen_c - 1
return False点评
想到查找就先想到了二分查找。先二分查找行中满足条件的，再从每一行中二分查找。
官方的Z字形查找还是更加巧妙一些。思路还是不够广。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog