algorithm - page - ¿Qué fila tiene más 1s en una matriz de 0-1 con todos los 1s "a la izquierda"?

weka homepage

Question

Problema

Cada fila de una matriz nxn consta de 1 y 0, de modo que en cualquier fila, todos los 1 preceden a los 0. Encuentra la fila que contiene la mayoría de los no en 1 en O (n).

Ejemplo

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

Encontré esta pregunta en mi libro de algoritmos. Lo mejor que pude hacer fue el tiempo O (n logn). ¿Cómo hacer esto en O (n)?

Answer 1

Cierto código C para hacer esto.

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 2

Comience con la primera fila. Mantenga la fila R que tenga la mayor cantidad de 1s y el índice i del último 1 de R en cada iteración compara la fila actual con la fila R en el índice i . si la fila actual tiene un 0 en la posición i , la fila R sigue siendo la respuesta. De lo contrario, devuelve el índice de la fila actual. Ahora solo tenemos que encontrar el último 1 de la fila actual. Itere del índice i hasta el último 1 de la fila actual, establezca R en esta fila y i en este nuevo índice.

              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 3

Comience en 1,1.

Si la celda contiene 1, estás en la fila más larga hasta el momento; escríbelo y ve a la derecha. Si la celda contiene 0, baje. Si la celda está fuera de límites, ya terminaste.

Answer 4

Puedes hacerlo en O(N) siguiente manera:

Comience en A[i][j] con 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++

Cuando llegue a la última fila o a la última columna, el valor de j será la respuesta.

Pseudo código:

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 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;
}

Complejidad del tiempo => O (fila + col), en el peor de los casos Si cada fila tiene n-1 una, excepto la última fila que tiene n 1s, entonces tenemos que viajar hasta la última fila.