一尘不染

哪一行在0-1矩阵中具有最大的1,而所有1都在“左侧”?

algorithm

问题

nxn矩阵的每一行都由1和0组成,因此在任何行中,所有1都在任何0之前。查找包含O(n)中最多不包含1的行。

1 1 1 1 1 0  <- Contains maximum number of 1s, return index 1
1 1 1 0 0 0
1 0 0 0 0 0
1 1 1 1 0 0
1 1 1 1 0 0
1 1 0 0 0 0

我在算法书中找到了这个问题。我能做的最好的就是花O(n logn)的时间。如何在O(n)中做到这一点?


阅读 419

收藏
2020-07-28

共1个答案

一尘不染

从1,1开始。

如果单元格包含1,则表示您是目前为止最长的一行;写下来然后继续。如果单元格包含0,则向下移动。如果单元格超出范围,那么您就完成了。

2020-07-28