algorithm - una - matriz java filas columnas
Establezca cada celda en la matriz en 0 si esa fila o columna contiene un 0 (30)
Dada una matriz NxN con 0s y 1s. Establezca cada fila que contiene un 0 a todos los 0 sy configure cada columna que contiene un 0 a todos los 0 s.
Por ejemplo
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
resultados en
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
Un ingeniero de Microsoft me dijo que hay una solución que no requiere memoria extra, solo dos variables booleanas y una pasada, así que estoy buscando esa respuesta.
Por cierto, imagina que es una matriz de bits, por lo tanto, solo 1s y 0s permiten estar en la matriz.
Actualmente. Si solo desea ejecutar el algoritmo e imprimir los resultados (es decir, no restaurarlos, entonces esto se puede hacer fácilmente de una sola vez. El problema surge cuando intenta modificar la matriz a medida que ejecuta el algoritmo).
Aquí está mi solución Simplemente implica ANDing los valores de filas / columnas para un elemento de givein (i, j) e imprimiéndolo.
#include <iostream>
#include "stdlib.h"
void process();
int dim = 5;
bool m[5][5]{{1,0,1,1,1},{0,1,1,0,1},{1,1,1,1,1},{1,1,1,1,1},{0,0,1,1,1}};
int main() {
process();
return 0;
}
void process() {
for(int j = 0; j < dim; j++) {
for(int i = 0; i < dim; i++) {
std::cout << (
(m[0][j] & m[1][j] & m[2][j] & m[3][j] & m[4][j]) &
(m[i][0] & m[i][1] & m[i][2] & m[i][3] & m[i][4])
);
}
std::cout << std::endl;
}
}
Aquí tengo una solución, se ejecuta en una sola pasada y todo el procesamiento está "en su lugar" sin memoria adicional (salvo para aumentar la pila).
Utiliza la recursión para retrasar la escritura de ceros que, por supuesto, destruiría la matriz para las otras filas y cols:
#include <iostream>
/**
* The idea with my algorithm is to delay the writing of zeros
* till all rows and cols can be processed. I do this using
* recursion:
* 1) Enter Recursive Function:
* 2) Check the row and col of this "corner" for zeros and store the results in bools
* 3) Send recursive function to the next corner
* 4) When the recursive function returns, use the data we stored in step 2
* to zero the the row and col conditionally
*
* The corners I talk about are just how I ensure I hit all the row''s a cols,
* I progress through the matrix from (0,0) to (1,1) to (2,2) and on to (n,n).
*
* For simplicities sake, I use ints instead of individual bits. But I never store
* anything but 0 or 1 so it''s still fair ;)
*/
// ================================
// Using globals just to keep function
// call syntax as straight forward as possible
int n = 5;
int m[5][5] = {
{ 1, 0, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1 }
};
// ================================
// Just declaring the function prototypes
void processMatrix();
void processCorner( int cornerIndex );
bool checkRow( int rowIndex );
bool checkCol( int colIndex );
void zeroRow( int rowIndex );
void zeroCol( int colIndex );
void printMatrix();
// This function primes the pump
void processMatrix() {
processCorner( 0 );
}
// Step 1) This is the heart of my recursive algorithm
void processCorner( int cornerIndex ) {
// Step 2) Do the logic processing here and store the results
bool rowZero = checkRow( cornerIndex );
bool colZero = checkCol( cornerIndex );
// Step 3) Now progress through the matrix
int nextCorner = cornerIndex + 1;
if( nextCorner < n )
processCorner( nextCorner );
// Step 4) Finially apply the changes determined earlier
if( colZero )
zeroCol( cornerIndex );
if( rowZero )
zeroRow( cornerIndex );
}
// This function returns whether or not the row contains a zero
bool checkRow( int rowIndex ) {
bool zero = false;
for( int i=0; i<n && !zero; ++i ) {
if( m[ rowIndex ][ i ] == 0 )
zero = true;
}
return zero;
}
// This is just a helper function for zeroing a row
void zeroRow( int rowIndex ) {
for( int i=0; i<n; ++i ) {
m[ rowIndex ][ i ] = 0;
}
}
// This function returns whether or not the col contains a zero
bool checkCol( int colIndex ) {
bool zero = false;
for( int i=0; i<n && !zero; ++i ) {
if( m[ i ][ colIndex ] == 0 )
zero = true;
}
return zero;
}
// This is just a helper function for zeroing a col
void zeroCol( int colIndex ) {
for( int i=0; i<n; ++i ) {
m[ i ][ colIndex ] = 0;
}
}
// Just a helper function for printing our matrix to std::out
void printMatrix() {
std::cout << std::endl;
for( int y=0; y<n; ++y ) {
for( int x=0; x<n; ++x ) {
std::cout << m[y][x] << " ";
}
std::cout << std::endl;
}
std::cout << std::endl;
}
// Execute!
int main() {
printMatrix();
processMatrix();
printMatrix();
}
Buen desafío. Esta solución utiliza en cierta forma solo dos booleanos creados en la pila, pero los booleanos se crean varias veces en la pila, ya que la función es recursiva.
typedef unsigned short WORD;
typedef unsigned char BOOL;
#define true 1
#define false 0
BYTE buffer[5][5] = {
1, 0, 1, 1, 0,
0, 1, 1, 1, 0,
1, 1, 1, 1, 1,
1, 0, 1, 1, 1,
1, 1, 1, 1, 1
};
int scan_to_end(BOOL *h,BOOL *w,WORD N,WORD pos_N)
{
WORD i;
for(i=0;i<N;i++)
{
if(!buffer[i][pos_N])
*h=false;
if(!buffer[pos_N][i])
*w=false;
}
return 0;
}
int set_line(BOOL h,BOOL w,WORD N,WORD pos_N)
{
WORD i;
if(!h)
for(i=0;i<N;i++)
buffer[i][pos_N] = false;
if(!w)
for(i=0;i<N;i++)
buffer[pos_N][i] = false;
return 0;
}
int scan(int N,int pos_N)
{
BOOL h = true;
BOOL w = true;
if(pos_N == N)
return 0;
// Do single scan
scan_to_end(&h,&w,N,pos_N);
// Scan all recursive before changeing data
scan(N,pos_N+1);
// Set the result of the scan
set_line(h,w,N,pos_N);
return 0;
}
int main(void)
{
printf("Old matrix/n");
printf( "%d,%d,%d,%d,%d /n", (WORD)buffer[0][0],(WORD)buffer[0][1],(WORD)buffer[0][2],(WORD)buffer[0][3],(WORD)buffer[0][4]);
printf( "%d,%d,%d,%d,%d /n", (WORD)buffer[1][0],(WORD)buffer[1][1],(WORD)buffer[1][2],(WORD)buffer[1][3],(WORD)buffer[1][4]);
printf( "%d,%d,%d,%d,%d /n", (WORD)buffer[2][0],(WORD)buffer[2][1],(WORD)buffer[2][2],(WORD)buffer[2][3],(WORD)buffer[2][4]);
printf( "%d,%d,%d,%d,%d /n", (WORD)buffer[3][0],(WORD)buffer[3][1],(WORD)buffer[3][2],(WORD)buffer[3][3],(WORD)buffer[3][4]);
printf( "%d,%d,%d,%d,%d /n", (WORD)buffer[4][0],(WORD)buffer[4][1],(WORD)buffer[4][2],(WORD)buffer[4][3],(WORD)buffer[4][4]);
scan(5,0);
printf("New matrix/n");
printf( "%d,%d,%d,%d,%d /n", (WORD)buffer[0][0],(WORD)buffer[0][1],(WORD)buffer[0][2],(WORD)buffer[0][3],(WORD)buffer[0][4]);
printf( "%d,%d,%d,%d,%d /n", (WORD)buffer[1][0],(WORD)buffer[1][1],(WORD)buffer[1][2],(WORD)buffer[1][3],(WORD)buffer[1][4]);
printf( "%d,%d,%d,%d,%d /n", (WORD)buffer[2][0],(WORD)buffer[2][1],(WORD)buffer[2][2],(WORD)buffer[2][3],(WORD)buffer[2][4]);
printf( "%d,%d,%d,%d,%d /n", (WORD)buffer[3][0],(WORD)buffer[3][1],(WORD)buffer[3][2],(WORD)buffer[3][3],(WORD)buffer[3][4]);
printf( "%d,%d,%d,%d,%d /n", (WORD)buffer[4][0],(WORD)buffer[4][1],(WORD)buffer[4][2],(WORD)buffer[4][3],(WORD)buffer[4][4]);
system( "pause" );
return 0;
}
Esto escanea en un patrón como:
s,s,s,s,s
s,0,0,0,0
s,0,0,0,0
s,0,0,0,0
s,0,0,0,0
0,s,0,0,0
s,s,s,s,s
0,s,0,0,0
0,s,0,0,0
0,s,0,0,0
y así
Y luego cambiando los valores en este patrón al regresar en cada una de las funciones de escaneo. (De abajo hacia arriba):
0,0,0,0,c
0,0,0,0,c
0,0,0,0,c
0,0,0,0,c
c,c,c,c,c
0,0,0,c,0
0,0,0,c,0
0,0,0,c,0
c,c,c,c,c
0,0,0,c,0
y así
Bueno, se me ocurrió una solución de paso único, en el lugar (no recursiva) usando 4 bools y 2 contadores de bucle. No he logrado reducirlo a 2 bools y 2 ints, pero no me sorprendería si fuera posible. Hace alrededor de 3 lecturas y 3 escrituras de cada celda, y debería ser O (N ^ 2), es decir. lineal en el tamaño de la matriz.
Took me a couple of hours to puzzle this one out - I wouldn''t want to have to come up with it under the pressure of an interview! If I''ve made a booboo I''m too tired to spot it...
Um... I''m choosing to define "single-pass" as making one sweep through the matrix, rather than touching each value once! :-)
#include <stdio.h>
#include <memory.h>
#define SIZE 5
typedef unsigned char u8;
u8 g_Array[ SIZE ][ SIZE ];
void Dump()
{
for ( int nRow = 0; nRow < SIZE; ++nRow )
{
for ( int nColumn = 0; nColumn < SIZE; ++nColumn )
{
printf( "%d ", g_Array[ nRow ][ nColumn ] );
}
printf( "/n" );
}
}
void Process()
{
u8 fCarriedAlpha = true;
u8 fCarriedBeta = true;
for ( int nStep = 0; nStep < SIZE; ++nStep )
{
u8 fAlpha = (nStep > 0) ? g_Array[ nStep-1 ][ nStep ] : true;
u8 fBeta = (nStep > 0) ? g_Array[ nStep ][ nStep - 1 ] : true;
fAlpha &= g_Array[ nStep ][ nStep ];
fBeta &= g_Array[ nStep ][ nStep ];
g_Array[ nStep-1 ][ nStep ] = fCarriedBeta;
g_Array[ nStep ][ nStep-1 ] = fCarriedAlpha;
for ( int nScan = nStep + 1; nScan < SIZE; ++nScan )
{
fBeta &= g_Array[ nStep ][ nScan ];
if ( nStep > 0 )
{
g_Array[ nStep ][ nScan ] &= g_Array[ nStep-1 ][ nScan ];
g_Array[ nStep-1][ nScan ] = fCarriedBeta;
}
fAlpha &= g_Array[ nScan ][ nStep ];
if ( nStep > 0 )
{
g_Array[ nScan ][ nStep ] &= g_Array[ nScan ][ nStep-1 ];
g_Array[ nScan ][ nStep-1] = fCarriedAlpha;
}
}
g_Array[ nStep ][ nStep ] = fAlpha & fBeta;
for ( int nScan = nStep - 1; nScan >= 0; --nScan )
{
g_Array[ nScan ][ nStep ] &= fAlpha;
g_Array[ nStep ][ nScan ] &= fBeta;
}
fCarriedAlpha = fAlpha;
fCarriedBeta = fBeta;
}
}
int main()
{
memset( g_Array, 1, sizeof(g_Array) );
g_Array[0][1] = 0;
g_Array[0][4] = 0;
g_Array[1][0] = 0;
g_Array[1][4] = 0;
g_Array[3][1] = 0;
printf( "Input:/n" );
Dump();
Process();
printf( "/nOutput:/n" );
Dump();
return 0;
}
Entonces mi idea es usar los valores en la última fila / columna como un indicador para indicar si todos los valores en la columna / fila correspondiente son 1s.
Usando un escaneo Zig Zag a través de toda la matriz EXCEPTO la fila / columna final. En cada elemento, establece el valor en la fila / columna final en cuanto al Y lógico de sí mismo con el valor en el elemento actual. En otras palabras, si tocas un 0, la fila / columna final se establecerá en 0. Si lo haces en 1, el valor en la fila / columna final será 1 solo si ya fue 1. En cualquier caso, establezca el elemento actual en 0.
Cuando haya terminado, su última fila / columna debería tener 1 si la columna / fila correspondiente se llenó con 1s.
Haga un escaneo lineal a través de la última fila y columna y busque 1s. Establezca 1s en los elementos correspondientes en el cuerpo de la matriz donde la fila y la columna finales son 1s.
Codificarlo será complicado para evitar errores uno por uno, etc. pero debería funcionar de una sola vez.
Esto no se puede hacer de una vez ya que un solo bit tiene un efecto en los bits antes y después de cualquier orden. IOW Sea cual sea el orden en el que recorra el conjunto, más adelante puede encontrar un 0, lo que significa que debe volver atrás y cambiar un 1 anterior a un 0.
Actualizar
La gente parece pensar que al restringir N a algún valor fijo (digamos 8) puede resolver que se trata de una sola pasada. Bueno, eso es a) perder el punto yb) no la pregunta original. No publicaría una pregunta sobre la clasificación y esperaría una respuesta que comenzara "asumiendo que solo quieres ordenar 8 cosas ...".
Dicho esto, es un enfoque razonable si sabes que N está de hecho restringido a 8. Mi respuesta anterior responde a la pregunta original que no tiene tal restricción.
Mantenga una sola variable para realizar un seguimiento de lo que son todas las filas AND juntas.
Si una fila es -1 (todos los 1s), entonces haz que la siguiente fila sea una referencia a esa variable
Si una fila es todo menos, es 0. Puedes hacer todo en una sola pasada. Código Psuedo:
foreach (my $row) rows {
$andproduct = $andproduct & $row;
if($row != -1) {
zero out the row
} else {
replace row with a reference to andproduct
}
}
Eso debería hacerlo, en una sola pasada, pero aquí se supone que N es lo suficientemente pequeño como para que la CPU haga aritmética en una sola fila, de lo contrario será necesario pasar por cada fila para determinar si es todo 1s o no, creo. Pero dado que estás preguntando por algos y no restringiendo mi hardware, simplemente comenzaría mi respuesta con "Build a CPU that supports a N-bit arithmetic ..."
Aquí hay un ejemplo de cómo se puede hacer en C. Nota: argumento que los valores y arr juntos representan la matriz, y p y numproducto son mi iterador y las variables de producto AND se usan para implementar el problema. (Podría haber pasado por encima con aritmética de puntero para validar mi trabajo, ¡pero una vez fue suficiente!)
int main() {
int values[] = { -10, 14, -1, -9, -1 }; /* From the problem spec, converted to decimal for my sanity */
int *arr[5] = { values, values+1, values+2, values+3, values+4 };
int **p;
int numproduct = 127;
for(p = arr; p < arr+5; ++p) {
numproduct = numproduct & **p;
if(**p != -1) {
**p = 0;
} else {
*p = &numproduct;
}
}
/* Print our array, this loop is just for show */
int i;
for(i = 0; i < 5; ++i) {
printf("%x/n",*arr[i]);
}
return 0;
}
Esto produce 0, 0, 6, 0, 6, que es el resultado de las entradas dadas.
O en PHP, si la gente piensa que mis juegos de pila en C son trampas (te sugiero que no, porque debería ser capaz de almacenar la matriz de la manera que prefiera):
<?php
$values = array(-10, 14, -1, -9, -1);
$numproduct = 127;
for($i = 0; $i < 5; ++$i) {
$numproduct = $numproduct & $values[$i];
if($values[$i] != -1) {
$values[$i] = 0;
} else {
$values[$i] = &$numproduct;
}
}
print_r($values);
¿Me estoy perdiendo de algo?
No creo que sea factible. Cuando estás en el primer cuadrado y su valor es 1, no tienes forma de saber cuáles son los valores de los otros cuadrados en la misma fila y columna. Entonces debe verificarlos y si hay un cero, regrese al primer cuadrado y cambie su valor a cero. Recomiendo hacerlo en dos pasos: el primer pase recopila información sobre qué filas y columnas deben ponerse a cero (la información se almacena en una matriz, por lo que estamos usando algo de memoria adicional). El segundo pase cambia los valores. Sé que esa no es la solución que está buscando, pero creo que es una solución práctica. Las restricciones dadas por usted hacen que el problema no tenga solución.
Ok, estoy cansado ya que son las 3 AM, pero tengo un primer intento en el lugar con exactamente 2 pases en cada número en la matriz, entonces en O (NxN) y es lineal en el tamaño de la matriz.
Uso la 1ra columna y la primera fila como marcadores para saber dónde están las filas / columnas con solo 1. Entonces, hay 2 variables l y c para recordar si la primera fila / columna son todas las 1 también. Entonces el primer pase establece los marcadores y restablece el resto a 0.
El segundo pase establece 1 en los lugares donde las filas y cols están marcados para ser 1, y restablece 1ra línea / col dependiendo de l y c.
Dudo mucho que pueda hacerlo en 1 pase, ya que las casillas al principio dependen de los cuadrados al final. Quizás mi segundo pase se puede hacer más eficiente ...
import pprint
m = [[1, 0, 1, 1, 0],
[0, 1, 1, 1, 0],
[1, 1, 1, 1, 1],
[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1]]
N = len(m)
### pass 1
# 1 rst line/column
c = 1
for i in range(N):
c &= m[i][0]
l = 1
for i in range(1,N):
l &= m[0][i]
# other line/cols
# use line1, col1 to keep only those with 1
for i in range(1,N):
for j in range(1,N):
if m[i][j] == 0:
m[0][j] = 0
m[i][0] = 0
else:
m[i][j] = 0
### pass 2
# if line1 and col1 are ones: it is 1
for i in range(1,N):
for j in range(1,N):
if m[i][0] & m[0][j]:
m[i][j] = 1
# 1rst row and col: reset if 0
if l == 0:
for i in range(N):
m [i][0] = 0
if c == 0:
for j in range(1,N):
m [0][j] = 0
pprint.pprint(m)
Puedo hacerlo con dos variables enteras y dos pasadas (hasta 32 filas y columnas ...)
bool matrix[5][5] =
{
{1, 0, 1, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{1, 0, 1, 1, 1},
{1, 1, 1, 1, 1}
};
int CompleteRows = ~0;
int CompleteCols = ~0;
// Find the first 0
for (int row = 0; row < 5; ++row)
{
for (int col = 0; col < 5; ++col)
{
CompleteRows &= ~(!matrix[row][col] << row);
CompleteCols &= ~(!matrix[row][col] << col);
}
}
for (int row = 0; row < 5; ++row)
for (int col = 0; col < 5; ++col)
matrix[row][col] = (CompleteRows & (1 << row)) && (CompleteCols & (1 << col));
Si bien es imposible debido a las limitaciones, la manera más eficiente de hacerlo es cruzando la matriz en una superposición alternando filas y columnas, lo que haría un patrón similar a la colocación de ladrillos en zigzag:
-----
|----
||---
|||--
||||-
Con esto, iría en cada fila / columna, como se indica, y si encuentra un 0 en cualquier momento, establezca una variable booleana y vuelva a recorrer esa fila / columna, estableciendo las entradas a 0 a medida que avanza.
Esto no requerirá memoria extra, y solo usará una variable booleana. Desafortunadamente, si el borde "lejano" está configurado como 0, ese es el peor de los casos y recorre toda la matriz dos veces.
Traté de resolver este problema en C #.
He usado dos variables de bucle (i y j) aparte de la matriz real y n representando su dimensión
La lógica que probé es:
- Calcular AND para filas y columnas involucradas en cada cuadrado concéntrico de la matriz
- Guárdelo en sus celdas de esquina (las he almacenado en orden antihorario)
- Se usan dos variables bool para retener los valores de dos esquinas cuando se evalúa un cuadrado particular.
- Este proceso terminaría cuando el bucle externo (i) esté a mitad de camino.
- Evalúe los resultados de otras celdas basadas en las celdas de esquina (para el resto de i). Saltee las celdas de la esquina durante este proceso.
- Cuando llegue a n, todas las celdas tendrían su resultado, excepto las celdas de esquina.
- Actualiza las celdas de la esquina. Esta es una iteración adicional a la longitud de n / 2 además de la restricción de paso único mencionada en el problema.
Código:
void Evaluate(bool [,] matrix, int n)
{
bool tempvar1, tempvar2;
for (var i = 0; i < n; i++)
{
tempvar1 = matrix[i, i];
tempvar2 = matrix[n - i - 1, n - i - 1];
var j = 0;
for (j = 0; j < n; j++)
{
if ((i < n/2) || (((n % 2) == 1) && (i == n/2) && (j <= i)))
{
// store the row and col & results in corner cells of concentric squares
tempvar1 &= matrix[j, i];
matrix[i, i] &= matrix[i, j];
tempvar2 &= matrix[n - j - 1, n - i - 1];
matrix[n - i - 1, n - i - 1] &= matrix[n - i - 1, n - j - 1];
}
else
{
// skip corner cells of concentric squares
if ((j == i) || (j == n - i - 1)) continue;
// calculate the & values for rest of them
matrix[i, j] = matrix[i, i] & matrix[n - j - 1, j];
matrix[n - i - 1, j] = matrix[n - i - 1, n - i - 1] & matrix[n - j - 1, j];
if ((i == n/2) && ((n % 2) == 1))
{
// if n is odd
matrix[i, n - j - 1] = matrix[i, i] & matrix[j, n - j - 1];
}
}
}
if ((i < n/2) || (((n % 2) == 1) && (i <= n/2)))
{
// transfer the values from temp variables to appropriate corner cells of its corresponding square
matrix[n - i - 1, i] = tempvar1;
matrix[i, n - i - 1] = tempvar2;
}
else if (i == n - 1)
{
// update the values of corner cells of each concentric square
for (j = n/2; j < n; j++)
{
tempvar1 = matrix[j, j];
tempvar2 = matrix[n - j - 1, n - j - 1];
matrix[j, j] &= matrix[n - j - 1, j];
matrix[n - j - 1, j] &= tempvar2;
matrix[n - j - 1, n - j - 1] &= matrix[j, n - j - 1];
matrix[j, n - j - 1] &= tempvar1;
}
}
}
}
crear una matriz de resultados y establecer todos los valores en 1. ir a través de la matriz de datos tan pronto como se encuentre un 0, establecer la columna de la fila de matriz de resultados en 0
Al final de la primera pasada, la matriz de resultados tendrá la respuesta correcta.
Parece bastante simple. ¿Hay algún truco que me falta? ¿No tienes permitido usar un conjunto de resultados?
EDITAR:
Parece una función F #, pero eso es un poco engañoso, ya que a pesar de que estás haciendo una sola pasada, la función puede ser recursiva.
Parece que el entrevistador está tratando de averiguar si conoce la programación funcional.
el problema puede ser resuelto de una sola pasada
guardando la matriz en una matriz i X j.
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
one each pass save the values of i and j for an element which is 0 in arrays a and b
when first row is scanned a= 1 b = 2,5
when second row is scanned a=1,2 b= 1,2,5
when third row is scanned no change
when fourth row is scanned a= 1,2,4 and b= 1,2,5
when fifth row is scanned no change .
Ahora imprime todos los valores como 0 para los valores de i y j guardados en a y b el resto de los valores son 1, es decir, (3,3) (3,4) (5,3) y (5,4)
1 pass, 2 booleans. I just have to assume the integer indexes in the iterations don''t count.
This is not a complete solution but I can''t get pass this point.
If I could only determine if a 0 is an original 0 or a 1 that was converted to a 0 then I wouldn''t have to use -1''s and this would work.
My output is like this:
-1 0 -1 -1 0
0 -1 -1 -1 0
-1 -1 1 1 -1
-1 0 -1 -1 -1
-1 -1 1 1 -1
The originality of my approach is using the first half of the examination of a row or column to determine if it contains a 0 and the last half to set the values - this is done by looking at x and width-x and then y and height-y in each iteration. Based on the results of the first half of the iteration, if a 0 in the row or column was found, I use the last half of the iteration to change the 1''s to -1''s.
I just realized this could be done with only 1 boolean leaving 1 to ...?
I''m posting this hoping someone might say, "Ah, just do this..." (And I spent way too much time on it not to post.)
Here''s the code in VB:
Dim D(,) As Integer = {{1, 0, 1, 1, 1}, {0, 1, 1, 0, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {0, 0, 1, 1, 1}}
Dim B1, B2 As Boolean
For y As Integer = 0 To UBound(D)
B1 = True : B2 = True
For x As Integer = 0 To UBound(D)
// Scan row for 0''s at x and width - x positions. Halfway through I''ll konw if there''s a 0 in this row.
//If a 0 is found set my first boolean to false.
If x <= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
If D(x, y) = 0 Or D(UBound(D) - x, y) = 0 Then B1 = False
End If
//If the boolean is false then a 0 in this row was found. Spend the last half of this loop
//updating the values. This is where I''m stuck. If I change a 1 to a 0 it will cause the column
//scan to fail. So for now I change to a -1. If there was a way to change to 0 yet later tell if
//the value had changed this would work.
If Not B1 Then
If x >= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
If D(x, y) = 1 Then D(x, y) = -1
If D(UBound(D) - x, y) = 1 Then D(UBound(D) - x, y) = -1
End If
End If
//These 2 block do the same as the first 2 blocks but I switch x and y to do the column.
If x <= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
If D(y, x) = 0 Or D(y, UBound(D) - x) = 0 Then B2 = False
End If
If Not B2 Then
If x >= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
If D(y, x) = 1 Then D(y, x) = -1
If D(y, UBound(D) - x) = 1 Then D(y, UBound(D) - x) = -1
End If
End If
Next
Next
Otra solución que requiere dos pases, es acumular AND horizontal y verticalmente:
1 0 1 1 0 | 0
0 1 1 1 0 | 0
1 1 1 1 1 | 1
1 0 1 1 1 | 0
1 1 1 1 1 | 1
----------+
0 0 1 1 0
Pensé que podría diseñar tal algoritmo usando bits de paridad , códigos Hamming o programación dinámica , posiblemente usando esos dos booleanos como un número de 2 bits, pero aún no he tenido éxito.
¿Puede volver a verificar la declaración del problema con su ingeniero y avisarnos? Si de hecho hay una solución, quiero seguir eliminando el problema.
De acuerdo, esta es una solución que
- usa solo un valor extra largo para el almacenamiento de trabajo.
- no usa recursividad
- un pase de solo N, ni siquiera N * N.
- funcionará para otros valores de N pero necesitará nuevos #defines.
#include <stdio.h> #define BIT30 (1<<24) #define COLMASK 0x108421L #define ROWMASK 0x1fL
unsigned long long STARTGRID =
((0x10 | 0x0 | 0x4 | 0x2 | 0x0) << 20) |
((0x00 | 0x8 | 0x4 | 0x2 | 0x0) << 15) |
((0x10 | 0x8 | 0x4 | 0x2 | 0x1) << 10) |
((0x10 | 0x0 | 0x4 | 0x2 | 0x1) << 5) |
((0x10 | 0x8 | 0x4 | 0x2 | 0x1) << 0);
void dumpGrid (char* comment, unsigned long long theGrid) {
char buffer[1000];
buffer[0]=''/0'';
printf ("/n/n%s/n",comment);
for (int j=1;j<31; j++) {
if (j%5!=1)
printf( "%s%s", ((theGrid & BIT30)==BIT30)? "1" : "0",(((j%5)==0)?"/n" : ",") );
theGrid = theGrid << 1;
}
}
int main (int argc, const char * argv[]) {
unsigned long long rowgrid = STARTGRID;
unsigned long long colGrid = rowgrid;
unsigned long long rowmask = ROWMASK;
unsigned long long colmask = COLMASK;
dumpGrid("Initial Grid", rowgrid);
for (int i=0; i<5; i++) {
if ((rowgrid & rowmask)== rowmask) rowgrid |= rowmask;
else rowgrid &= ~rowmask;
if ((colGrid & colmask) == colmask) colmask |= colmask;
else colGrid &= ~colmask;
rowmask <<= 5;
colmask <<= 1;
}
colGrid &= rowgrid;
dumpGrid("RESULT Grid", colGrid);
return 0;
}
Here is my Ruby implementation with the the test included, This would take O(MN) space. If we want a real time update (like to show the results when we find zeros rather than waiting the first loop of finding zeros) we can just create another class variable like @output and whenever we find a zero we update @output and not @input .
require "spec_helper"
class Matrix
def initialize(input)
@input = input
@zeros = []
end
def solve
@input.each_with_index do |row, i|
row.each_with_index do |element, j|
@zeros << [i,j] if element == 0
end
end
@zeros.each do |x,y|
set_h_zero(x)
set_v_zero(y)
end
@input
end
private
def set_h_zero(row)
@input[row].map!{0}
end
def set_v_zero(col)
@input.size.times do |r|
@input[r][col] = 0
end
end
end
describe "Matrix" do
it "Should set the row and column of Zero to Zeros" do
input = [[1, 3, 4, 9, 0],
[0, 3, 5, 0, 8],
[1, 9, 6, 1, 9],
[8, 3, 2, 0, 3]]
expected = [[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 9, 6, 0, 0],
[0, 0, 0, 0, 0]]
matrix = Matrix.new(input)
expect(matrix.solve).to eq(expected)
end
end
No one is using binary forms? since it''s only 1 and 0. We can use binary vectors.
def set1(M, N):
''''''Set 1/0s on M according to the rules.
M is a list of N integers. Each integer represents a binary array, e.g.,
000100''''''
ruler = 2**N-1
for i,v in enumerate(M):
ruler = ruler & M[i]
M[i] = M[i] if M[i]==2**N-1 else 0 # set i-th row to all-0 if not all-1s
for i,v in enumerate(M):
if M[i]: M[i] = ruler
return M
Here''s the test:
M = [ 0b10110,
0b01110,
0b11111,
0b10111,
0b11111 ]
print "Before..."
for i in M: print "{:0=5b}".format(i)
M = set1(M, len(M))
print "After..."
for i in M: print "{:0=5b}".format(i)
Y el resultado:
Before...
10110
01110
11111
10111
11111
After...
00000
00000
00110
00000
00110
Ok, I realize that it isn''t quite a match, but I got it in one pass using a bool and a byte instead of two bools... close. I also wouldn''t vouch for the efficiency of it but these types of questions often require less than optimal solutions.
private static void doIt(byte[,] matrix)
{
byte zeroCols = 0;
bool zeroRow = false;
for (int row = 0; row <= matrix.GetUpperBound(0); row++)
{
zeroRow = false;
for (int col = 0; col <= matrix.GetUpperBound(1); col++)
{
if (matrix[row, col] == 0)
{
zeroRow = true;
zeroCols |= (byte)(Math.Pow(2, col));
// reset this column in previous rows
for (int innerRow = 0; innerRow < row; innerRow++)
{
matrix[innerRow, col] = 0;
}
// reset the previous columns in this row
for (int innerCol = 0; innerCol < col; innerCol++)
{
matrix[row, innerCol] = 0;
}
}
else if ((int)(zeroCols & ((byte)Math.Pow(2, col))) > 0)
{
matrix[row, col] = 0;
}
// Force the row to zero
if (zeroRow) { matrix[row, col] = 0; }
}
}
}
One Pass - I have traversed the input only once but used a new array and only two extra Boolean variables.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
boolean rowDel = false, colDel = false;
int arr[][] = new int[n][n];
int res[][] = new int[n][n];
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
arr[i][j] = sc.nextInt();
res[i][j] = arr[i][j];
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (arr[i][j] == 0)
colDel = rowDel = true; //See if we have to delete the
//current row and column
if (rowDel == true){
res[i] = new int[n];
rowDel = false;
}
if(colDel == true){
for (int k = 0; k < n; k++) {
res[k][j] = 0;
}
colDel = false;
}
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
System.out.print(res[i][j]);
}
System.out.println();
}
sc.close();
}
One matrix scan, two booleans, no recursion.
How to avoid the second pass? The second pass is needed to clear the rows or columns when the zero appeares at their end.
However this problem can be solved, because when we scan row #i we already know the row status for the row #i-1. So, while we are scanning the row #i we can simultaneously clear the row #i-1 if it is needed.
The same solution works for columns, but we need to scan rows and columns simultaneously while the data is not changed by the next iteration.
Two booleans are required to store the status of first row and first column, because their values will be changed during the execution of main part of the algorithm.
To avoid adding more booleans we are storing the "clear" flag for the rows and columns in the first row and column of the matrix.
public void Run()
{
const int N = 5;
int[,] m = new int[N, N]
{{ 1, 0, 1, 1, 0 },
{ 1, 1, 1, 1, 0 },
{ 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1 }};
bool keepFirstRow = (m[0, 0] == 1);
bool keepFirstColumn = keepFirstRow;
for (int i = 1; i < N; i++)
{
keepFirstRow = keepFirstRow && (m[0, i] == 1);
keepFirstColumn = keepFirstColumn && (m[i, 0] == 1);
}
Print(m); // show initial setup
m[0, 0] = 1; // to protect first row from clearing by "second pass"
// "second pass" is performed over i-1 row/column,
// so we use one more index just to complete "second pass" over the
// last row/column
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
// "first pass" - searcing for zeroes in row/column #i
// when i = N || j == N it is additional pass for clearing
// the previous row/column
// j >= i because cells with j < i may be already modified
// by "second pass" part
if (i < N && j < N && j >= i)
{
m[i, 0] &= m[i, j];
m[0, j] &= m[i, j];
m[0, i] &= m[j, i];
m[j, 0] &= m[j, i];
}
// "second pass" - clearing the row/column scanned
// in the previous iteration
if (m[i - 1, 0] == 0 && j < N)
{
m[i - 1, j] = 0;
}
if (m[0, i - 1] == 0 && j < N)
{
m[j, i - 1] = 0;
}
}
Print(m);
}
// Clear first row/column if needed
if (!keepFirstRow || !keepFirstColumn)
{
for (int i = 0; i < N; i++)
{
if (!keepFirstRow)
{
m[0, i] = 0;
}
if (!keepFirstColumn)
{
m[i, 0] = 0;
}
}
}
Print(m);
Console.ReadLine();
}
private static void Print(int[,] m)
{
for (int i = 0; i < m.GetLength(0); i++)
{
for (int j = 0; j < m.GetLength(1); j++)
{
Console.Write(" " + m[i, j]);
}
Console.WriteLine();
}
Console.WriteLine();
}
The code below creates a matrix of size m,n. First decide the dimensions of the matrix. I wanted to fill the matrix[m][n] with randomly with numbers between 0..10. Then create another matrix of the same dimensions and fill it with -1s (final matrix). Then iterate through the initial matrix to see if you will hit 0. When you hit on location(x,y), go to the final matrix and fill the row x with 0s and column y with 0s. At the end read through the final matrix, if the value is -1 (original value) copy the value in the same location of the initial matrix to final.
public static void main(String[] args) {
int m = 5;
int n = 4;
int[][] matrixInitial = initMatrix(m, n); // 5x4 matrix init randomly
int[][] matrixFinal = matrixNull(matrixInitial, m, n);
for (int i = 0; i < m; i++) {
System.out.println(Arrays.toString(matrixFinal[i]));
}
}
public static int[][] matrixNull(int[][] matrixInitial, int m, int n) {
int[][] matrixFinal = initFinal(m, n); // create a matrix with mxn and init it with all -1
for (int i = 0; i < m; i++) { // iterate in initial matrix
for (int j = 0; j < n; j++) {
if(matrixInitial[i][j] == 0){ // if a value is 0 make rows and columns 0
makeZeroX(matrixFinal, i, j, m, n);
}
}
}
for (int i = 0; i < m; i++) { // if value is -1 (original) copy from initial
for (int j = 0; j < n; j++) {
if(matrixFinal[i][j] == -1) {
matrixFinal[i][j] = matrixInitial[i][j];
}
}
}
return matrixFinal;
}
private static void makeZeroX(int[][] matrixFinal, int x, int y, int m, int n) {
for (int j = 0; j < n; j++) { // make all row 0
matrixFinal[x][j] = 0;
}
for(int i = 0; i < m; i++) { // make all column 0
matrixFinal[i][y] = 0;
}
}
private static int[][] initMatrix(int m, int n) {
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
Random rn = new Random();
int random = rn.nextInt(10);
matrix[i][j] = random;
}
}
for (int i = 0; i < m; i++) {
System.out.println(Arrays.toString(matrix[i]));
}
System.out.println("******");
return matrix;
}
private static int[][] initFinal(int m, int n) {
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = -1;
}
}
return matrix;
}
// another approach
/**
* @param matrixInitial
* @param m
* @param n
* @return
*/
private static int[][] matrixNullNew(int[][] matrixInitial, int m, int n) {
List<Integer> zeroRowList = new ArrayList<>(); // Store rows with 0
List<Integer> zeroColumnList = new ArrayList<>(); // Store columns with 0
for (int i = 0; i < m; i++) { // read through the matrix when you hit 0 add the column to zeroColumnList and add
// the row to zeroRowList
for (int j = 0; j < n; j++) {
if (matrixInitial[i][j] == 0) {
if (!zeroRowList.contains(i)) {
zeroRowList.add(i);
}
if (!zeroColumnList.contains(j)) {
zeroColumnList.add(j);
}
}
}
}
for (int a = 0; a < m; a++) {
if (zeroRowList.contains(a)) { // if the row has 0
for (int b = 0; b < n; b++) {
matrixInitial[a][b] = 0; // replace all row with zero
}
}
}
for (int b = 0; b < n; b++) {
if (zeroColumnList.contains(b)) { // if the column has 0
for (int a = 0; a < m; a++) {
matrixInitial[a][b] = 0; // replace all column with zero
}
}
}
return matrixInitial;
}
The simplest solution I can think of is pasted below. The logic is to record which row and column to set zero while iterating.
import java.util.HashSet;
import java.util.Set;
public class MatrixExamples {
public static void zeroOut(int[][] myArray) {
Set<Integer> rowsToZero = new HashSet<>();
Set<Integer> columnsToZero = new HashSet<>();
for (int i = 0; i < myArray.length; i++) {
for (int j = 0; j < myArray.length; j++) {
if (myArray[i][j] == 0) {
rowsToZero.add(i);
columnsToZero.add(j);
}
}
}
for (int i : rowsToZero) {
for (int j = 0; j < myArray.length; j++) {
myArray[i][j] = 0;
}
}
for (int i : columnsToZero) {
for (int j = 0; j < myArray.length; j++) {
myArray[j][i] = 0;
}
}
for (int i = 0; i < myArray.length; i++) { // record which rows and // columns will be zeroed
for (int j = 0; j < myArray.length; j++) {
System.out.print(myArray[i][j] + ",");
if(j == myArray.length-1)
System.out.println();
}
}
}
public static void main(String[] args) {
int[][] a = { { 1, 0, 1, 1, 0 }, { 0, 1, 1, 1, 0 }, { 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1 }, { 1, 1, 1, 1, 1 } };
zeroOut(a);
}
}
This is TESTED for different N in C++, and is:
ONE PASS , TWO BOOLS , NO RECURSION , NO EXTRA MEMORY , HOLDS FOR ARBITRARLY LARGE N
(So far none of the solutions here do ALL of these.)
More specifically, I''m amusing two loop counters are okay. I have two const unsigneds, which only exist rather than being computed every time for readability. The outer loop''s interval is [0, N], and the inner loop''s interval is [1, n - 1]. The switch statement is in the loop mostly exists to show very clearly that it really is just one pass.
Algorithm Strategy:
The first trick is to us a row and a column from the matrix itself to accumulate the content of the matrix, this memory becomes available by offloading all we really need to know from the first row and column into two booleans. The second trick is to get two passes out of one, by using the symmetry of the sub-matrix and its indices.
Algorithm Synopsis:
- Scan the first row and store if they are all ones in a boolean, do the same for the first column storing the result in a second boolean.
- For the sub-matrix excluding the first row and the first column: iterate through, left to right, top to bottom, as one would read a paragraph. Upon visiting each element, also visit the corresponding element that would be visited if visiting the sub-matrix in reverse. For each element visited AND its value into the where its row crosses the first column, and also AND its value into where its column crosses the first row.
- Once the center of the sub-matrix is reached, continue to visit the two elements simultaneously as above. However now set the visited elements'' value to the AND of where its row crosses the first column, and of where its column crosses the first row. After this, the sub-matrix is complete.
- Use the two boolean variables computed at the begging to set the first row, and the first column to their correct values.
Templatized C++ Implementation:
template<unsigned n>
void SidewaysAndRowColumn(int((&m)[n])[n]) {
bool fcol = m[0][0] ? true : false;
bool frow = m[0][0] ? true : false;
for (unsigned d = 0; d <= n; ++d) {
for (unsigned i = 1; i < n; ++i) {
switch (d) {
case 0:
frow = frow && m[d][i];
fcol = fcol && m[i][d];
break;
default:
{
unsigned const rd = n - d;
unsigned const ri = n - i;
if (d * n + i < rd * n + ri)
{
m[ d][ 0] &= m[ d][ i];
m[ 0][ d] &= m[ i][ d];
m[ 0][ i] &= m[ d][ i];
m[ i][ 0] &= m[ i][ d];
m[rd][ 0] &= m[rd][ri];
m[ 0][rd] &= m[ri][rd];
m[ 0][ri] &= m[rd][ri];
m[ri][ 0] &= m[ri][rd];
}
else
{
m[ d][ i] = m[ d][0] & m[0][ i];
m[rd][ri] = m[rd][0] & m[0][ri];
}
break;
}
case n:
if (!frow)
m[0][i] = 0;
if (!fcol)
m[i][0] = 0;
};
}
}
m[0][0] = (frow && fcol) ? 1 : 0;
}
You can do something like this to use one pass but an input and output matrix:
output(x,y) = col(xy) & row(xy) == 2^n
where col(xy) is the bits in the column containing the point xy ; row(xy) is the bits in the row containing the point xy . n is the size of the matrix.
Then just loop over the input. Possibly expandable to be more space efficient?
You can sorta do it in one pass -- if you don''t count accessing the matrix in random-access order, which eliminates the benefits of doing it single-pass in the first place (cache-coherence/memory-bandwidth).
[edit: simple, but wrong solution deleted]
You should get better performance than any single-pass method by doing it in two passes: one to accumulate row/column info, and one to apply it. The array (in row-major order) is accessed coherently; for arrays exceeding the cache size (but whose rows can fit in cache), data should be read from memory twice, and stored once:
void fixmatrix2(int M[][], int rows, int cols) {
bool clearZeroRow= false;
bool clearZeroCol= false;
for(int j=0; j < cols; ++j) {
if( ! M[0][j] ) {
clearZeroRow= true;
}
}
for(int i=1; i < rows; ++i) { // scan/accumulate pass
if( ! M[i][0] ) {
clearZeroCol= true;
}
for(int j=1; j < cols; ++j) {
if( ! M[i][j] ) {
M[0][j]= 0;
M[i][0]= 0;
}
}
}
for(int i=1; i < rows; ++i) { // update pass
if( M[i][0] ) {
for(int j=0; j < cols; ++j) {
if( ! M[j][0] ) {
M[i][j]= 0;
}
}
} else {
for(int j=0; j < cols; ++j) {
M[i][j]= 0;
}
}
if(clearZeroCol) {
M[i][0]= 0;
}
}
if(clearZeroRow) {
for(int j=0; j < cols; ++j) {
M[0][j]= 0;
}
}
}
here is my solution. As you can see from the code, given a M * N matrix, it sets the entire row to zero once it inspects a zero in that row.the time complexity of my solution is O(M * N) . I am sharing the whole class which has a static populated array for testing and a display array method to see the result in the console.
public class EntireRowSetToZero {
static int arr[][] = new int[3][4];
static {
arr[0][0] = 1;
arr[0][1] = 9;
arr[0][2] = 2;
arr[0][3] = 2;
arr[1][0] = 1;
arr[1][1] = 5;
arr[1][2] = 88;
arr[1][3] = 7;
arr[2][0] = 0;
arr[2][1] = 8;
arr[2][2] = 4;
arr[2][3] = 4;
}
public static void main(String[] args) {
displayArr(EntireRowSetToZero.arr, 3, 4);
setRowToZero(EntireRowSetToZero.arr);
System.out.println("--------------");
displayArr(EntireRowSetToZero.arr, 3, 4);
}
static int[][] setRowToZero(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
if(arr[i][j]==0){
arr[i]=new int[arr[i].length];
}
}
}
return arr;
}
static void displayArr(int[][] arr, int n, int k) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println("");
}
}
}
i hope you enjoy my 1-pass c# solution
you can retrieve an element with O(1) and only need the space of one row and one column of the matrix
bool[][] matrix =
{
new[] { true, false, true, true, false }, // 10110
new[] { false, true, true, true, false }, // 01110
new[] { true, true, true, true, true }, // 11111
new[] { true, false, true, true, true }, // 10111
new[] { true, true, true, true, true } // 11111
};
int n = matrix.Length;
bool[] enabledRows = new bool[n];
bool[] enabledColumns = new bool[n];
for (int i = 0; i < n; i++)
{
enabledRows[i] = true;
enabledColumns[i] = true;
}
for (int rowIndex = 0; rowIndex < n; rowIndex++)
{
for (int columnIndex = 0; columnIndex < n; columnIndex++)
{
bool element = matrix[rowIndex][columnIndex];
enabledRows[rowIndex] &= element;
enabledColumns[columnIndex] &= element;
}
}
for (int rowIndex = 0; rowIndex < n; rowIndex++)
{
for (int columnIndex = 0; columnIndex < n; columnIndex++)
{
bool element = enabledRows[rowIndex] & enabledColumns[columnIndex];
Console.Write(Convert.ToInt32(element));
}
Console.WriteLine();
}
/*
00000
00000
00110
00000
00110
*/
seems like the following works with no additional space requirements:
first note that multiplying the elements of the row times the elements of the line in which an element is, gives the desired value.
In order not to use any additional space (not making a new matrix and filling it up but instead apply changes to the matrix directly), start top left of the matrix and do the computation for any ixi matrix (that "starts" at (0,0)) before considering any element with any index > i.
hope this works (havent testet)