中淼建设工程有限公司网站,北碚区建设银行网站,wordpress去视频广告插件,商城站到商城汽车站1.问题描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性#xff1a;
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
示例#xff1a; 输入#xff1a;matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10…1.问题描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
示例 输入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
输出false2.难度等级
Medium。
3.热门指数
★★★★☆
4.解题思路
方法一直接查找
我们直接遍历整个矩判断 target 是否出现即可。
时间复杂度 O(mn)。
空间复杂度 O(1)。
下面以 Golang 为例给出实现。
func searchMatrix(matrix [][]int, target int) bool {for _, row : range matrix {for _, v : range row {if v target {return true}}}return false
}方法二二分查找
由于矩阵中每一行的元素都是升序排列的因此我们可以对每一行都二分查找判断 targett 是否在该行中。
时间复杂度 O(mlogn)。对一行使用二分查找的时间复杂度为 O(logn)最多需要进行 m 次二分查找。
空间复杂度 O(1)。
下面以 Golang 为例给出实现。
func searchMatrix(matrix [][]int, target int) bool {for _, row : range matrix {i : sort.SearchInts(row, target)if i len(row) row[i] target {return true}}return false
}方法三Z 字形查找
上面的两个方法效率并不高效实际上还有线性时间复杂度的解法。
矩阵有两个特性
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
那么我们可以比较明显得感知到这两个特性就会是我们解开这个题的关键所在了。
们以示例一的矩阵作为例子如果我们以某一个边角作为出发点那么我们会得出如下结论
【左上角】从左到右升序排列从上到下升序排列
【右上角】从右到左降序排列从上到下升序排列
【左下角】从左到右升序排列从下到上降序排列
【右上角】从右到左降序排列从下到上降序排列具体情况请见下图所示 通过上面我们的分析可以发现左下角和右上角这两个出发点才是我们解题的关键因为这两个点在水平方向移动和在垂直方向移动分别是递增或者递减的那么我们就可以执行如下逻辑
【如果当前格子的值 小于 target】那么就向递增方向移动
【如果当前格子的值 大于 target】那么就向递减方向移动
【如果当前格子的值 等于 target】那么返回 true
【如果移动 越界 并且 不等于 target】那么返回 false下面以左下角为例从左下角开始搜索 5。当然从右上角搜索也是可以的。 时间复杂度 O(mn)。最坏情况下是从右上角搜索到左下角遍历了 mn 个元素。
空间复杂度 O(1)。
下面以 Golang 为例给出实现。
func searchMatrix(matrix [][]int, target int) bool {m, n : len(matrix), len(matrix[0])// 从左下角开始搜索。x, y : m-1, 0for x 0 y n {if matrix[x][y] target {return true}if matrix[x][y] target {x--} else {y}}return false
}参考文献
240. 搜索二维矩阵II - LeetCode
