百度面试算法题求解～

2016/9/24镜像同步10 回复

今天面百度面到一道很奇怪的算法题。一个二维数组行数m，列数n，每一行是递增的，第一列是递增的，其他列不保证递增（我反复确认了），写一个查找算法找到目标数，要求最坏复杂度小于O(mlogn)。百思不得其解，求大神指教。

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

ztinpn机器人#1 · 2016/9/24

每行第一个数最小，最后数最大，先根据这个判断目标数在哪一行。最坏情况是它可能在每一行，m种情况，那就每行搞个二分查找，所以是mlogn

leontp机器人#2 · 2016/9/24

我也是说的是这个思路，但是面试官说还可以优化[ema8] 【在 ztinpn 的大作中提到: 】 : 每行第一个数最小，最后数最大，先根据这个判断目标数在哪一行。最坏情况是它可能在每一行，m种情况，那就每行搞个二分查找，所以是mlogn

ztinpn机器人#3 · 2016/9/24

【在 leontp 的大作中提到: 】 : 我也是说的是这个思路，但是面试官说还可以优化第一列是递增的这个信息也用上了？

leihangwang机器人#4 · 2016/9/24

第一列是递增的，可以排除掉比target大的行？

leontp机器人#5 · 2016/9/24

用了，而且这个不能改变最坏情况的吧。【在 ztinpn 的大作中提到: 】 : : 第一列是递增的这个信息也用上了？

nuanyangyang机器人#6 · 2016/9/25

为什么别的列不递增呢？如果别的列递增。有O（m+n）的算法如果只是第一列递增去，和没有这个条件没什么区别吧。

Sluggard机器人#7 · 2016/9/30

别的列也要递增才有O(M + N)的算法。

dxy1机器人#8 · 2016/9/30

【在 leihangwang 的大作中提到: 】 : 第一列是递增的，可以排除掉比target大的行？应该吧，但是最坏的还是没有改变啊，是不是要看下m，n的数量级？

a895981819机器人#9 · 2016/9/30

如果每一列都是递增，每一行都是递增，那么可以从右上角开始判断？这样复杂度是o（m+n）发自「贵邮」