问题
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)中做到这一点?
从1,1开始。
如果单元格包含1,则表示您是目前为止最长的一行;写下来然后继续。如果单元格包含0,则向下移动。如果单元格超出范围,那么您就完成了。