非死不可新鲜店面跪经

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

llatjob 发表于 2020-5-12 10:54
每行bst找到最后一个0，loop每一行，找最小index。时间复杂度 O(mlogn)

这个方法对于列数n 远大于行数m时是最佳的。

mchzh 发表于 2020-5-12 08:16
需要用bit吗，只需要从右上角开始遍历就可以吧，往左走或者往下走

我也觉得无需bit。
这个“往左走或者往下走”方法对于行数M远大于列数N时是最佳的。（否则对于每行binary search最佳）

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

zzgzzm 发表于 2020-5-12 11:48
我也觉得无需bit。
这个“往左走或者往下走”方法对于行数M远大于列数N时是最佳的。（否则对于每行binar ...

你说的这个解释有理，行数和列数之间的比例可以选择不同的方法去trade-off

ywangriley 发表于 2020/05/12 12:50:31
对的，就是saddle back search，二维sorted search题很多都可以用。但全1的情况是右上直接往左...

老哥说的是左下和右上同时开始找吗？
这个想法很棒，有点像双向搜索

qiaofengmarco 发表于 2020-5-12 09:23
从右上角开始，逐行找最0，找到第一个0跳到下一行。时间复杂度O(M+N)

补充内容 (2020-5-11 18:23):

最坏的情况，还是O(MN)