Problem
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Example 1:
1 | Input: |
Example 2:
1 | Input: |
Analysis
这道题是一道关于搜索算法的题目,在给定的一个矩阵中,搜索target
是否存在。最直接的做法就是双重循环遍历数组,但是这样的做法显然是低效的。我们可以利用矩阵本身的一些特性来优化搜索的算法。
根据题目的描述,我们可以总结出,数组中行内是有序的,且行间也是有序的。我们可以通过比较每一行中的最后一个元素来定位target
可能存在的行,然后再对该行遍历就可以了。
Solution
如果target
在第i
行中,那么它一定满足target > matrix[i-1][n-1] && target <= matrix[i][n-1]
。这里需要注意特殊情况,即target
在第一行。同时,还要注意越界的情况。
注意row
初始化为INT_MAX
,这里保证如果target
比矩阵中所有的数都大时,我们能够判断出来。
Code
1 | class Solution { |
运行时间:约8ms,超过97.55%的CPP代码。
Summary
这道题是关于搜索算法比较新颖的一题,以往一般会使用二分查找来提高搜索效率。其实这题也是利用了同样的思想,利用矩阵本身的有序性,对比关键元素的值,缩窄搜索范围,最终搜得结果。这道题的分析到此为止,谢谢您的支持!