搜索二维矩阵:Z 字查找与二分
哪些公司问过
答案要点
- Z 字查找:从右上角出发,大于目标则左移,小于目标则下移,O(m+n)
- 每步排除一行或一列,空间 O(1);左下角出发同理
- 二分:对每行二分 O(m log n),或先二分定位行再行内二分
- 若整个矩阵展开后有序,可当作一维数组整体二分 O(log(m×n))
- 先确认矩阵的有序条件,不同条件最优解不同
易错点
- 把两种矩阵条件混为一谈
- 从左上角开始,无法决定移动方向
- 边界移动后没有判断越界
- 逐行遍历 O(m×n),没有用上有序性
面试官常见追问
- 为什么从右上角开始?
- 两种矩阵条件有什么区别?
- Z 字查找的时间复杂度为什么是 O(m+n)?
- 如果要找出所有的出现位置怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。