arrays - 给定一个按行排序的 bool 矩阵。返回最大数量为 1 的行

Question

我遇到了一个矩阵问题，但我正试图找出最佳解决方案。问题陈述是问题主题本身。进一步见下文

Example
Input matrix

  0 1 1 1
  0 0 1 1
  1 1 1 1  // this row has maximum 1s
  0 0 0 0

Output: 2

我的解决方案:现在由于行已排序，我想在每行中第一次出现 1 时执行二进制搜索，然后 1 的计数将是总列数减去1st 1 的索引。

这将在 O(m*logn) 内完成，但我很想知道这是否可以在线性时间内完成的逻辑。

谢谢!

Answer 1

在右上角开始一个光标。在每一行中，向左走，直到到达该行的最后一个。然后下台。如果您下台并且光标指向 0，请再次下台。永远不要走错。您正在寻找最左边有 1 的行，因此您永远不需要向右看。运行时间为 O(n+m)，因为您遍历每一行，向下移动 m 次，并且总共最多剩下 n 步。下面是一些伪代码，假设矩阵是列表的列表:

bestrow = 0
leftmost = matrix.width

for i = matrix.height to 0:
    row = matrix[i]
    while row[leftmost - 1] == 1:
        leftmost--
        bestrow = i

return bestrow

如果按字面意思翻译代码，您可能会遇到全 0 矩阵或某行全 1 的问题。这些都非常容易处理，伪代码的目的只是传达通用算法。