哪一行拥有最多1秒的0-1矩阵，全1＆QUOT;左边＆QUOT;？

问题描述

问题

的N×N矩阵的每行由1和0的，使得在任何行，全部为1来之前任何0。找到包含行大部分为O（n）。没有1的

Each row of an n x n matrix consists of 1's and 0's such that in any row, all 1's come before any 0's. Find row containing most no of 1's in O(n).

示例

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）？

I found this question in my algorithms book. The best I could do took O(n logn) time.How to do this in O(n)?

推荐答案

开始在1,1。

如果单元格中包含1，你在最长的行为止;把它写下来，向右走。如果单元格包含0，往下走。如果细胞是出界，你就大功告成了。

If the cell contains 1, you're on the longest row so far; write it down and go right.If the cell contains 0, go down.If the cell is out of bounds, you're done.

这篇关于哪一行拥有最多1秒的0-1矩阵，全1＆QUOT;左边＆QUOT;？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！