0-1 矩阵中哪一行的 1 最多，且所有 1 都在“左侧”？

Question

问题

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) 内做到这一点？

Answer 1

从 1,1 开始。

如果单元格包含 1，则您位于迄今为止最长的行；写下来然后向右走。
如果单元格包含 0，则向下。
如果单元格超出范围，则完成。

Answer 2

您可以在 O(N) 中完成此操作，如下所示：

从 A[i][j] 开始，使用 i=j=0。

          1, keep moving to the right by doing j++
A[i][j] = 
          0, move down to the next row by doing i++

当您到达最后一行或最后一列时，j 的值将是答案。

伪代码：

Let R be number of rows
Let C be number of columns

Let i = 0
Let j = 0   
Let max1Row = 0

while ( i<R && j<C )
   if ( matrix[i][j] == 1 )
      j++
      max1Row = i
   else
      i++
end-while


print "Max 1's = j"
print "Row number with max 1's = max1Row"

Answer 3

从第一行开始。保留 1 数量最多的行 R 以及 R 最后一个 1 的索引 i。在每次迭代中，将当前行与索引 i 上的行 R 进行比较。如果当前行在位置 i 上有 0，则行 R 仍然是答案。
否则，返回当前行的索引。现在我们只需找到当前行的最后 1 个即可。从索引 i 迭代到当前行的最后 1 个，将 R 设置为该行，并将 i 设置为这个新索引。

              i
              |  
              v 
R->   1 1 1 1 1 0  
|
v     1 1 1 0 0 0 (Compare ith index of this row)
      1 0 0 0 0 0         Repeat
      1 1 1 1 0 0           "
      1 1 1 1 0 0           "
      1 1 0 0 0 0           "

Answer 4

一些 C 代码可以做到这一点。

int n = 6;
int maxones = 0, maxrow = -1, row = 0, col = 0;
while(row < n) {
    while(col < n && matrix[row][col] == 1) col++;
    if(col == n) return row;
    if(col > maxones){
        maxrow = row;
        maxones = col;
    }
    row++;
}

Answer 5

int [] getMax1withRow(int [][] matrix){
    int [] result=new int[2];
    int rows=matrix.length;
    int cols=matrix[0].length;
    int i=0, j=0;
    int max_row=0;// This will show row with maximum 1. Intialing pointing to 0th row.
    int max_one=0;// max one
    while(i< rows){
        while(matrix[i][j]==1){
            j++;
        }
        if(j==n){
             result[0]=n;
             result[1]=i;
             return result;
        }
        if(j>max_one){
             max_one=j;
             max_row=i;
        }
        j=0;// Again start from the first column
        i++;// increase row number
    }
    result[0]=max_one;
    result[1]=max_row;
    return result;
}

时间复杂度=> O(row+col)，在最坏的情况下，如果除了最后一行有 n 个 1 之外，每行都有 n-1 个，那么我们必须行进到最后一行。