问题
n x n矩阵的每一行都由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)中做到这一点？
最佳答案
从1,1开始。
如果单元格包含1，则表示您是目前为止最长的一行；写下来然后继续。
如果单元格包含0，则向下移动。
如果单元格超出范围，那么您就完成了。
关于algorithm - 哪一行在0-1矩阵中的全1数最大，且全1？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5388571/