c++ - 在二维矩阵中找到最大为0的行

问题



例



输出量



我的点子

如果0的每一行都是连续的，我们可以从每一行的两端进行扫描。常识说使用O(n^2)进行扫描。

有没有O(n)解决方案？

最佳答案

如果每一行都像1 .... 10 ... 0，则可以对每一行中的第一个零进行二进制搜索。

那将是O(n * lg(n))

对于任意矩阵，必须检查每个单元格，因此它必须为O(n ^ 2)。