题目
在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下:
1
2
3
4
5
6
7 [
[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
。给定
target = 20
,返回false
。限制:
0 <= n <= 1000
0 <= m <= 1000
注意:本题与主站 240 题相同:https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
从左上到右下都是单增,该数组每行每列都是排序数组,因此比较直观地认为可以使用一些搜索算法,比如二分查找。
暴力法
遍历数组。
优化
对每一行二分查找。
还可以再优化,先判断该数是否在该行的区间内。
不过时间复杂度也就是$NlogM$。
1 | class Solution { |
差一点就想到的优化
只想到了从左上或者右下开始,但是因为并没能很好地缩小搜索区域而放弃。
实际上从左下和右上开始搜索,每次可以排除一行或一列。
事实上,由于每行从左向右递增,每列自上而下递增,我们可以把一个7型排列的数组元素看作是一行,而拐角元素为某个中间值,而与中间值比较,选取左右区间,实际上将一个二维数组重新排列成$min(m,n)$个一维数组,按顺序在这些数组中二分查找目标元素。
而以上思路再具体到这道题目中,就是与(例如)右上元素比较,等于则命中,小于则在该元素所在行左侧寻找,大于则在元素所在列下方寻找,但并不一定就在这个范围内。而我们能够确定的,是它一定不在另外一侧,因此收缩搜索区域。
这种方法并不容易想到,所以需要从简单的例子入手去发现规律。
1 | class Solution { |
递归的实现竟然更慢,其时间复杂度为$O(M+N)$。
迭代实现
递归的实现,其思路为缩小搜索范围。
而迭代的实现,其思路为从(例如)右上角元素出发,每次选择一个方向寻找,等于则返回,大于则向下,小于则向左。