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.