A 2d matrix is given filled with 1's and 0's. It is given that all 1's in a row come before all the 0's. We have to find the maximum number of 1's in a row.
我已经制定了解决方案,我们可以在每一行上应用二进制搜索,以在 0 开始之前获取该行中最后一个 1 的最后一个索引,从而获得编号。 1的将是它的索引+1。所以我们可以在每一行都这样做。 所以复杂度为 O(mlogn),其中 m 是编号。行和 n 是没有。的列。 有没有更好的解决方案?
最佳答案
可以在 O(n+m) 中完成。
从 curmax 等于 0 开始。
然后逐行处理。当该行中至少有 curmax 个时,增加 curmax,即检查 curmax 值是否为 1。
在处理完所有行后,答案将是第 curmax-th。
这将在 O(n+m) 中起作用。
它会比 O(m*logn) 更快吗?这取决于。如果 m 小于 n/(log(n) - 1),它将起作用,实际上比 O(m*log n) 更长,否则更快,只是在复杂性方面。
在近似时间时考虑常数是另一个问题。所以对于一个数量级的 n 和 m 这会更快,对于不同的只有一个选择 - 尝试两者,选择更好的。
关于algorithm - 找出连续 1 的最大数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10054677/