asp网站添加背景音乐,生鲜配送网站建设,网络交友的网站建设,网站制作技术方案编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性#xff1a;
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
示例 1#xff1a; 输入#xff1a;matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,…编写一个高效的算法来搜索 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.lengthn matrix[i].length1 n, m 300-109 matrix[i][j] 109每行的所有元素从左到右升序排列每列的所有元素从上到下升序排列-109 target 109
Python代码
直接从右上角到左下角进行遍历即可如果想不到这个方法就只能每一行进行而分查找了这样的话就是O(mlogn)而直接右上角到左下角则是O(mn)
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) - bool:m len(matrix)n len(matrix[0])i 0j n-1while im and j0:if matrix[i][j]target:return Trueelif matrix[i][j]target:j-1else:i1return False
