Leetcode 第240题 Search a 2D Matrix II【分而治之】(Java)
原题地址： https://leetcode.com/problems/search-a-2d-matrix-ii/
写一个高效的算法来搜索m*n的矩阵，该矩阵有如下属性：
- 每行整数从左到右升序排列
- 每列整数从上到下升序排列
例子：
针对如下矩阵
[
[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]
]
如果目标是5，返回 true
如果目标是20，返回 false
这道题我尝试了4种解法：横竖分别搜索，横竖分别双向二分查找，四块分别查找，先排序再二分查找。
横竖分别搜索
这个思路相对来说比较直接，也是分而治之。首先把矩阵竖向分割，分为上下，分后在竖向分割为上下，直到只剩下一个行，则在行里面使用二分查找。这个思路比较像mergesort+二分查找。
运行时间是52ms，还不够快，因为我们只利用了矩阵的一条属性，就是从左到右生序排列。纵向的顺序我们没有利用到。
横竖分别横向二分查找
我们需要在纵横两个方面都加二分查找才能更快。那么我们把矩阵分成上下两半的时候，我们观察到两个关键点，上面矩阵的右下角 p1 ，如果 target 比它大，我们就不必搜索上面矩阵了。下面矩阵的左上角 p2 ，如果 target 比它小，我们也不必搜索下面矩阵了。如下图：
在代码中 p1 即为 matrix[mid][matrix[mid].length-1] ， p2 为 matrix[mid+1][0] 。所以代码如下：
执行时间是27ms，还不够快。
四块分别查找
我其实知道可以写成四块分别查找，但是我一直避免，因为太麻烦了，很容易写乱。上面一个方案还不够快，我就不得不写这个方案了。思路并不复杂，就是把矩阵分成4块，横竖各自一刀。然后再每个矩阵里面再次迭代的切分，直到最后切到只有一个元素为止。因为矩阵的属性左小右大，上小下大，我们就可以根据几个关键点判断target是否存在来判断这个子矩阵要不要进入，从而提速。每个子矩阵的左上和右下都是关键点。
这个思路不难，但是代码麻烦的要死。但是你仔细观察，这个实现就很类似于《算法导论》第四章的Strassen矩阵乘法的例子。下面是代码：
运行时间是7ms，这个效率应该是足够了。
先排序再二分查找
前面的思路都太辛苦，能不能简单的实现这个问题呢？我之前尝试了一下，我把整个矩阵展开成一个一维数组，然后二分查找不是很简单么？而且我都不用真的展开，我直接写一个一维坐标和二维坐标的转换不就可以了么？但是我还是太天真。矩阵虽然有这两个属性，但是不能保证从左到右，然后从上到下是有序的。所以，这个方法失败。
那么我们只好把矩阵复制到一个一位数组，然后排序，然后二分查找。代码如下：
代码相当好理解，可惜效率不行，运行时间为610ms，爆表了……所以这个方法不可取，还是第三个解决方案效果最好，虽然代码看着就累。
Github 地址： https://github.com/tinyfool/leetcode/tree/master/src/p0240
也请参阅我的文章《 LeetCode专题 分而治之 》，文章中实现了算法导论里面的这三个分而治之的问题的代码，以及LeetCode相关问题的一个列表。
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
