概述
题目难度: 简单
原题链接
今天继续更新剑指 offer 系列, 这道题的优化空间非常大, 个人感觉很适合作为面试题, 值得一做. 大家在我的公众号"每日精选算法题"中的聊天框中回复 offer 就能看到该系列当前已经更新的文章了
大家有什么想法建议和反馈的话欢迎随时交流, 包括但不限于公众号聊天框/知乎私信评论等等~
题目描述
在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
0 <= n <= 1000
0 <= m <= 1000
题目样例
示例
现有矩阵 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。
-
给定 target = 20,返回 false。
题目思考
- 如何充分利用两个递增条件?
解决方案
思路
分析
- 相信大家都不难想出暴力遍历所有数字和二分查找每行的方法, 前者时间复杂度为
O(RC)
, 后者有所优化, 达到了O(RlogC)
. (R
和C
分别代表行和列的数目) - 当然, 对于二分查找, 我们还可以稍作优化. 因为行和列都是递增, 所以二分查找既可以横向查找, 也可以纵向查找, 具体选哪种就看行数还是列数更多: 行数多的话就纵向查找, 否则横向查找. 这样就充分利用了二分查找对数复杂度的特性, 减小较大项对速度的影响, 使得复杂度降低为
O(min(R,C)*log(max(R,C)))
- 但到这里大部分面试官可能都还不满意, 会追问有没有更优的方案. 因为即使是上面的二分查找, 也只用到了行或列递增的单一条件, 没有把两个递增条件同时用上, 我们如何同时用上这两个条件呢?
推导
- 回顾两个递增性质, 假设当前我们遍历到的下标为
(r,c)
, 那么它和 target 的关系可以分为下面三种情况:- 值等于 target, 直接返回 true 即可
- 值小于 target, 那么以该点为右下角的左上矩形中的所有值都必然小于 target, 可以安全被排除, 而其余部分则说不好
- 值大于 target, 正好与上面相反, 以该点为左上角端点的右下矩形都可以被排除
- 重点关注上面的两个排除关系, 我们如果可以从某个起点开始, 一次排除一片区域, 然后朝一个方向继续线性遍历, 这样很快就能排查完整个矩阵
- 而为了满足线性遍历的条件, 起点的可选值只能是左下角或者右上角, 这里可以用反证法证明: 假设我们从矩阵左上角或右下角或中间某个地方开始的话, 排除完一块区域后, 我们接下来总有两个方向选择: 排除了右下矩阵, 则可以向左或者向上继续遍历, 同理排除左上矩阵也会有向右和向下两个方向可选.
- 而如果起点选在左下角或者右上角, 情况就不同了, 只会有一种选择. 这里以左下角起点为例, 我们可以通过递推来得出结论:
- 如果初始值小于 target, 因为下边没元素, 所以只能向右不能向下;
- 如果初始值大于 target, 因为左边没元素, 所以只能向上不能向左;
- 如果第一步操作是向右, 那么第二个值如果小于 target, 还只能向右, 因为下边仍然没元素; 而如果大于 target, 还只能向上, 因为左边的整列都已经在上一次被排除掉了, 结果不可能存在于左边
- 而如果第一步操作是向上, 按照同样的分析, 仍然可得还是只能向右或者向上继续遍历
- 以此类推, 每次都是要么向右, 要么向上, 就能排查完矩阵所有的数字得出结果
实现
- 初始化坐标为左下角(当然右上角也可以, 大家可以想想看代码要怎么改), 然后判断当前点与 target 的关系, 大于的话行号减 1, 小于的话列号+1, 直到找到等于 target 的点, 或者超出矩阵范围
- 下面代码中对必要的步骤都有注释, 方便大家理解
复杂度
- 时间复杂度
O(R+C)
- 循环每次要么行号-1, 要么列号+1, 最多只用循环 R+C 次
- 空间复杂度
O(1)
- 只使用了几个变量
代码
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]],
target: int) -> bool:
if not matrix:
return False
rows, cols = len(matrix), len(matrix[0])
# 起点为左下角
r, c = rows - 1, 0
while r >= 0 and c < cols:
if matrix[r][c] > target:
# 大于target, 向上
r -= 1
elif matrix[r][c] < target:
# 小于target, 向右
c += 1
else:
# 找到target, 返回True
return True
# 遍历整个矩阵都找不到, 返回False
return False
大家可以在下面这些地方找到我~????
我的知乎专栏
我的 CSDN
我的 Leetcode
我的牛客网博客
我的公众号: 每日精选算法题, 欢迎大家扫码关注~????
最后
以上就是风趣日记本为你收集整理的[leetcode 剑指offer系列] 面试题04. 二维数组中的查找的全部内容,希望文章能够帮你解决[leetcode 剑指offer系列] 面试题04. 二维数组中的查找所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复