给定一个按行排序的布尔矩阵.返回最大数为1的行

Question

我遇到了Matrices的一个问题,但我正试图找出最佳解决方案.问题陈述是问题主题本身.进一步见下文

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 total number of columns minus index of 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.这些很容易处理,伪代码的重点只是传达通用算法.