algorithm - 找出连续 1 的最大数量

Question

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 是没有。的列。有没有更好的解决方案？

Answer 1

可以在 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 这会更快，对于不同的只有一个选择 - 尝试两者，选择更好的。