调试中...
中等
相关标签
相关企业
提示
给定 M×N 矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。
示例：
现有矩阵 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。
通过次数
25.4K
提交次数
57.3K
通过率
44.4%
相关企业
提示 1
先试试一种简单解法。但希望不要太简单。你应该能够借助矩阵是有序的这一实际情况。
提示 2
可以在每一行进行二进制搜索。这需要多长时间？怎样才能做得更好？
提示 3
如果你正在考虑某个特定列，是否有办法快速消除该列（至少在某些情况下）？
提示 4
由于每列都进行了排序，因此如果该值小于此列中的最小值，则可知该值不能位于此列中。除此以外还能告诉你什么？
提示 5
如果值x小于列的开头，那么它也不能在右边的任何列中。
提示 6
考虑行中的上一个提示。
提示 7
如果我们试图使用一个数组来记录它，会发生什么？这有什么优点和缺点呢？
提示 8
可以使用前面的提示在行和列上向上、向下、向左和向右移动吗？
提示 9
另一种方法是，如果你沿着单元格画一个矩形一直延伸到底部，那么矩阵右坐标所在的单元格将大于这个矩形中所有的单元格。
提示 10
每个单元格的数会小于其下方和右侧的所有数，会大于其上方和左侧的所有数。如果我们想在第一轮排除最多元素，应该将x与哪个元素进行比较？
提示 11
如果将x与矩阵中的中心元素进行比较，我们可以排除大约四分之一的元素。
评论 (0)
《程序员面试金典（第 6 版）》独家授权
本书是原谷歌资深面试官的经验之作，帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的，帮助你轻松应战 IT 名企技术面试。
© 2025 领扣网络（上海）有限公司
0 人在线