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]p2matrix[mid+1][0]。所以代码如下:

执行时间是27ms,还不够快。

四块分别查找

我其实知道可以写成四块分别查找,但是我一直避免,因为太麻烦了,很容易写乱。上面一个方案还不够快,我就不得不写这个方案了。思路并不复杂,就是把矩阵分成4块,横竖各自一刀。然后再每个矩阵里面再次迭代的切分,直到最后切到只有一个元素为止。因为矩阵的属性左小右大,上小下大,我们就可以根据几个关键点判断target是否存在来判断这个子矩阵要不要进入,从而提速。每个子矩阵的左上和右下都是关键点。

这个思路不难,但是代码麻烦的要死。但是你仔细观察,这个实现就很类似于《算法导论》第四章的Strassen矩阵乘法的例子。下面是代码:

运行时间是7ms,这个效率应该是足够了。

先排序再二分查找

前面的思路都太辛苦,能不能简单的实现这个问题呢?我之前尝试了一下,我把整个矩阵展开成一个一维数组,然后二分查找不是很简单么?而且我都不用真的展开,我直接写一个一维坐标和二维坐标的转换不就可以了么?但是我还是太天真。矩阵虽然有这两个属性,但是不能保证从左到右,然后从上到下是有序的。所以,这个方法失败。

那么我们只好把矩阵复制到一个一位数组,然后排序,然后二分查找。代码如下:

代码相当好理解,可惜效率不行,运行时间为610ms,爆表了……所以这个方法不可取,还是第三个解决方案效果最好,虽然代码看着就累。

Github 地址:https://github.com/tinyfool/leetcode/tree/master/src/p0240

也请参阅我的文章《LeetCode专题 分而治之》,文章中实现了算法导论里面的这三个分而治之的问题的代码,以及LeetCode相关问题的一个列表。

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据