数组、二分搜索二维矩阵
程序员文章站
2024-01-28 12:25:28
1、题目描述https://leetcode-cn.com/problems/search-a-2d-matrix/编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数(变成了240题的特例)。通用模板就看LeetCode240:搜索二维矩阵IIhttps://blog.csdn.net/IOT_victor/article/details/104642324本题解法在.....
1、题目描述
https://leetcode-cn.com/problems/search-a-2d-matrix/
编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。
该矩阵具有如下特性:
每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数(变成了240题的特例)。
通用模板就看 LeetCode240:搜索二维矩阵II https://blog.csdn.net/IOT_victor/article/details/104642324
本题解法在240基础上加了优化
2、代码详解
法一:缩小领域法
因为每一行递增,每一列递增。所以我们可以从右上角往左下角找或者从左下角往右上角找。
每次比较可以排除一行或者一列,时间复杂度为O(m+n)
class Solution(object):
def searchMatrix(self, matrix, target):
# m * n
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
# 左下角(必须这么设置!左下角:最后一行的最小值)从下向上
row = m - 1
col = 0
while row >= 0 and col <= n-1:
# 优化:当前行的最大值 < target
if matrix[row][n-1] < target:
return False
if matrix[row][col] > target:
row -= 1
elif matrix[row][col] < target:
col += 1
else:
return True
return False
# # 右上角(必须这么设置!右上角:第一行的最大值)从上向下
# row = 0 # 行
# col = n - 1 # 列
# while row <= m-1 and col >= 0:
# # 优化:当前行的最小值 > target
# if matrix[row][0] > target:
# return False
# if matrix[row][col] > target: # 在本行中
# col -= 1
# elif matrix[row][col] < target: # 加行
# row += 1
# else:
# return True
# return False
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
s = Solution()
print(s.searchMatrix(matrix, target))
法二:标准的二分查找模板
将二维矩阵拖为一维矩阵,然后就是一个有序的一维数组了,利用二分查找就行
本文地址:https://blog.csdn.net/IOT_victor/article/details/107081728
下一篇: python基础学习(十三)