行列都递增的二维矩阵中查找目标值
哪些公司问过
答案要点
- 利用行列递增,从右上角或左下角开始
- 当前值大于目标则排除当前列,小于目标则排除当前行
- 每步排除一行或一列,时间 O(m+n),空间 O(1)
- 从左上角或右下角出发无法判断排除方向
- 备选:逐行二分 O(m log n);暴力 O(mn)
易错点
- 从左上角开始,无法排除
- 忘了处理空矩阵
- 把完全有序和行列分别有序两种情况混淆
面试官常见追问
- 如果整个矩阵按行展开后是完全有序的呢?
- 为什么从右上角出发可行?
- 需要返回目标出现次数怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。