在O(n)时间复杂度内找出具有最多1的行

Question

可能是重复问题：
只有1和0的矩阵

给定一个NxN的数组，它由只包含1和0的元素组成，每行中所有的1都在0之前。

- ano

Answer 1

我之前在SO上看到过一个类似的问题，如果有人找到链接，请编辑一下。 编辑：找到链接了：只包含1和0的矩阵。解决方案如下：

1. Start in the first row, most-left column
2. Go right until you hit a 0, if so, go down
3. If you hit a 1, the current row will be your new "best row"
4. Repeat from 2 until you either hit the bottom or the right border

给定一个NxN的数组，最好情况下检查N个单元格，最坏情况下检查N*2-1个单元格，因此从行/列的角度看，它是O(N)的时间复杂度。

- schnaader

Answer 2

你的作业解决方案是：

从第一行的第一个单元格开始。如果它包含1，则移动到同一行中的下一个单元格。如果它包含0，则移动到下一行中的同一单元格。重复此过程，直到处理完所有行。

你最后一次在行内移动的行是具有最大数量的1的行。

- Codo