Establezca cada celda en la matriz en 0 si esa fila o columna contiene un 0
https://stackoverflow.com/questions/339262
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Dada una matriz NxN con 0s y 1s. Establezca cada fila que contenga un 0 en todos los 0 sy configure cada columna que contenga un 0 en 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
resulta 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 adicional, 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 se permiten 1s y 0s en la matriz.
Solución
Ok, entonces estoy cansado ya que son las 3 AM aquí, 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.
Utilizo la primera 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 también son todas de 1. 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 los puntos están marcados como 1, y restablece la primera línea / punto dependiendo de l y c.
Dudo mucho que pueda hacerse en 1 pasada ya que los cuadrados al principio dependen de los cuadrados al final. Tal vez mi segundo pase pueda ser 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)
Otros consejos
Esto no se puede hacer en una pasada ya que un solo bit tiene un efecto en los bits antes y después en cualquier orden. IOW Independientemente del orden en el que atravieses la matriz, es posible que luego encuentres un 0, lo que significa que debes retroceder y cambiar un 1 anterior a un 0.
Update
La gente parece pensar que al restringir N a un valor fijo (digamos 8) puede resolver esto es una 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 "suponiendo que solo desee ordenar 8 cosas ...".
Dicho esto, es un enfoque razonable si sabe que N de hecho está restringido a 8. Mi respuesta anterior responde a la pregunta original que no tiene esa restricción.
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.
Uso de un exploración en zigzag a través de toda la matriz, EXCEPTO La última fila / columna. En cada elemento, establece el valor en la fila / columna final en cuanto al AND lógico de sí mismo con el valor en el elemento actual. En otras palabras, si toca un 0, la fila / columna final se establecerá en 0. Si es un 1, el valor en la fila / columna final será 1 solo si ya era 1. En cualquier caso, establezca el elemento actual en 0.
Cuando haya terminado, su fila / columna final debería tener 1s 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 final y la columna son ambos 1s.
La codificación será difícil de evitar errores, etc., pero debería funcionar de una sola vez.
Tengo una solución aquí, se ejecuta en una sola pasada y realiza todo el procesamiento en su lugar " sin memoria adicional (salvo para aumentar la pila).
Utiliza la recursividad para retrasar la escritura de ceros que, por supuesto, destruiría la matriz para las otras filas y columnas:
#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();
}
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. Por lo tanto, debe verificarlos y, si hay un cero, volver al primer cuadrado y cambiar su valor a cero. Recomendaré hacerlo en dos pasos: el primer paso recopila información sobre qué filas y columnas se deben poner a cero (la información se almacena en una matriz, por lo que estamos usando algo de memoria adicional). La segunda pasada cambia los valores. Sé que esa no es la solución que estás buscando, pero creo que es práctica. Las restricciones dadas por usted hacen que el problema no tenga solución.
Puedo hacerlo con dos variables enteras y dos pases (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));
el problema se puede resolver de una sola vez
guardar 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)
Otra solución que requiere dos pasadas 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 dicho algoritmo usando bits de paridad , Códigos de 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 e informarnos? Si hay de hecho una solución, quiero seguir eliminando el problema.
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), haga que la siguiente fila sea una referencia a esa variable
Si una fila es cualquier cosa menos, es un 0. Puede hacer todo de una sola vez. Psuedo-código:
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 realice operaciones aritméticas en una sola fila, de lo contrario, tendrá que recorrer cada fila para determinar si es todo 1 o no, creo. Pero dado que está preguntando acerca de algos y no limita mi hardware, simplemente comenzaría mi respuesta con "Construir una CPU que admita aritmética de N bits ..."
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 numproduct son mi iterador y las variables de producto AND que se utilizan para implementar el problema. (Podría haber pasado por encima de arr 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 stack en C son trampas (te sugiero que no lo sea, porque debería poder almacenar la matriz de la forma 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 algo?
Buen desafío. Esta solución utiliza 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í sucesivamente
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í sucesivamente
Bien, esta es una solución que
- usa solo un valor extra largo para el almacenamiento de trabajo.
- no utiliza recursividad.
- una pasada 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;
}
En realidad. 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 mientras ejecuta el algoritmo.
Aquí está mi solución. Solo involucra ANDing los valores de filas / columnas para un elemento de givein (i, j) e imprimirlo.
#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;
}
}
Traté de resolver este problema en C #.
He usado dos variables de bucle (i y j) aparte de la matriz real yn representando su dimensión
La lógica que intenté es:
- Calcule AND para las filas y cols involucrados en cada cuadrado concéntrico de la matriz
- Almacénelo en sus celdas de la esquina (los he guardado en orden antihorario)
- Se utilizan dos variables bool para retener los valores de dos esquinas al evaluar un cuadrado en particular.
- Este proceso finalizaría cuando el bucle externo (i) esté a mitad de camino.
- Evaluar los resultados de otras celdas en función de las celdas de la esquina (para el resto de i). Omita las celdas de las esquinas durante este proceso.
- Cuando alcanzo n, todas las celdas tendrían su resultado, excepto las celdas de la esquina.
- Actualiza las celdas de la esquina. Esta es una iteración adicional a la longitud de n / 2 que no sea 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;
}
}
}
}
Si bien son imposibles dadas las limitaciones, la forma más eficiente de hacerlo es atravesando la matriz de una manera superpuesta, alternando fila / columna, lo que haría un patrón similar a la colocación de ladrillos en zig-zag:
-----
|----
||---
|||--
||||-
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 caminar esa fila / columna, estableciendo las entradas en 0 a medida que avanza .
Esto no requerirá memoria adicional y solo usará una variable booleana. Desafortunadamente, si el " lejos " edge está configurado para que todo sea 0, ese es el peor de los casos y recorre todo el conjunto dos veces.
crea una matriz de resultados y establece todos los valores en 1. ir a través de la matriz de datos tan pronto como se encuentre un 0, establezca la columna de fila de la 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 estoy perdiendo? ¿No tiene permiso para usar un conjunto de resultados?
EDITAR:
Parece una función F #, pero eso es un poco engañoso, ya que aunque esté haciendo una sola pasada, la función puede ser recursiva.
Parece que el entrevistador está tratando de averiguar si conoce la programación funcional.
Bueno, se me ocurrió una solución de un solo paso, in situ (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 debe ser O (N ^ 2), es decir. lineal en el tamaño de la matriz.
Me tomó un par de horas resolver esto: ¡no quisiera tener que pensarlo bajo la presión de una entrevista! Si he hecho un booboo, estoy demasiado cansado para detectarlo ...
Um ... elijo definir " single-pass " ¡como hacer un barrido a través de la matriz, en lugar de tocar cada valor una vez! :-)
#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;
}
Espero que disfrutes de mi solución C # de 1 paso
puede recuperar un elemento con O (1) y solo necesita el espacio de una fila y una columna de la matriz
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
*/
1 pase, 2 booleanos. Solo tengo que asumir que los índices enteros en las iteraciones no cuentan.
Esta no es una solución completa pero no puedo pasar este punto.
Si solo pudiera determinar si un 0 es un 0 original o un 1 que se convirtió en 0, entonces no tendría que usar -1 y esto funcionaría.
Mi salida es así:
-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
La originalidad de mi enfoque es usar la primera mitad del examen de una fila o columna para determinar si contiene un 0 y la última mitad para establecer los valores; esto se hace mirando xy ancho-x y luego y y height-y en cada iteración. Según los resultados de la primera mitad de la iteración, si se encuentra un 0 en la fila o columna, utilizo la última mitad de la iteración para cambiar los 1 a -1.
Me acabo de dar cuenta de que esto se puede hacer con solo 1 booleano dejando 1 para ...?
Estoy publicando esto esperando que alguien pueda decir: "Ah, solo haz esto ..." (Y pasé demasiado tiempo para no publicar).
Aquí está el código en 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
¿Nadie está usando formas binarias? ya que es solo 1 y 0. Podemos usar vectores binarios.
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
Aquí está la prueba:
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 la salida:
Before...
10110
01110
11111
10111
11111
After...
00000
00000
00110
00000
00110
Puede hacer algo como esto para usar una pasada pero una matriz de entrada y salida:
output(x,y) = col(xy) & row(xy) == 2^n
donde col (xy) son los bits en la columna que contiene el punto xy ; row (xy) son los bits en la fila que contienen el punto xy . n es el tamaño de la matriz.
Luego, simplemente repita la entrada. ¿Posiblemente expandible para ser más eficiente en el espacio?
Un escaneo matricial, dos booleanos, sin recursividad.
¿Cómo evitar el segundo pase? La segunda pasada es necesaria para borrar las filas o columnas cuando el cero aparece al final.
Sin embargo, este problema se puede resolver, porque cuando escaneamos la fila #i ya sabemos el estado de la fila # i-1. Entonces, mientras escaneamos la fila #i, podemos borrar simultáneamente la fila # i-1 si es necesario.
La misma solución funciona para columnas, pero necesitamos escanear filas y columnas simultáneamente mientras la próxima iteración no cambia los datos.
Se requieren dos booleanos para almacenar el estado de la primera fila y la primera columna, porque sus valores se cambiarán durante la ejecución de la parte principal del algoritmo.
Para evitar agregar más booleanos, estamos almacenando el " clear " marca para las filas y columnas en la primera fila y columna de la matriz.
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();
}
parece que lo siguiente funciona sin requisitos de espacio adicionales:
primera nota que al multiplicar los elementos de la fila por los elementos de la línea en la que se encuentra un elemento, se obtiene el valor deseado.
Para no usar ningún espacio adicional (no hacer una nueva matriz y llenarla, sino aplicar cambios directamente a la matriz), comience arriba a la izquierda de la matriz y calcule cualquier matriz ixi (que "comienza" ; en (0,0)) antes de considerar cualquier elemento con cualquier índice > i.
espero que esto funcione (havent testet)
Esto es PROBADO para diferentes N en C ++, y es:
ONE PASS , DOS BOOLS , NO HAY RECURSIÓN , NO HAY MEMORIA EXTRA , SOPORTE PARA ARBITRARMENTE GRANDE N
(Hasta ahora, ninguna de las soluciones aquí hace TODAS estas).
Más específicamente, me divierte que dos contadores de bucle estén bien. Tengo dos constantes sin firmar, que solo existen en lugar de ser calculadas cada vez para facilitar la lectura. El intervalo del bucle externo es [0, N], y el intervalo del bucle interno es [1, n - 1]. La declaración de cambio está en el bucle sobre todo existe para mostrar muy claramente que realmente es solo una pasada.
Estrategia de algoritmo:
El primer truco es para nosotros una fila y una columna de la matriz para acumular el contenido de la matriz, esta memoria está disponible al descargar todo lo que realmente necesitamos saber de la primera fila y columna en dos booleanos. El segundo truco es obtener dos pases de uno, utilizando la simetría de la submatriz y sus índices.
Sinopsis del algoritmo:
- Escanee la primera fila y almacene si todos están en un booleano, haga lo mismo para la primera columna que almacena el resultado en un segundo booleano.
- Para la submatriz que excluye la primera fila y la primera columna: repita, de izquierda a derecha, de arriba a abajo, como se leería un párrafo. Al visitar cada elemento, también visite el elemento correspondiente que se visitaría si visitara la submatriz en reversa. Para cada elemento visitado Y su valor en donde su fila cruza la primera columna, y también Y su valor en donde su columna cruza la primera fila.
- Una vez que se alcanza el centro de la submatriz, continúe visitando los dos elementos simultáneamente como se indicó anteriormente. Sin embargo, ahora establezca el valor de los elementos visitados en el AND de donde su fila cruza la primera columna y de donde su columna cruza la primera fila. Después de esto, la submatriz está completa.
- Use las dos variables booleanas calculadas al inicio para establecer la primera fila y la primera columna a sus valores correctos.
Implementación de C ++ templada:
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;
}
Ok, me doy cuenta de que no es un buen partido, pero lo obtuve de una sola vez usando un bool y un byte en lugar de dos bools ... cerca. Tampoco respondería por la eficacia, pero este tipo de preguntas a menudo requieren soluciones menos que óptimas.
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; }
}
}
}
Puede hacerlo en una sola pasada: si no cuenta el acceso a la matriz en orden de acceso aleatorio, lo que elimina los beneficios de hacerlo de una sola pasada en primer lugar (coherencia de caché / ancho de banda de memoria ).
[edit: solución simple pero incorrecta eliminada]
Debería obtener un mejor rendimiento que cualquier método de una sola pasada al hacerlo en dos pasadas: una para acumular información de fila / columna y otra para aplicarla. Se accede a la matriz (en orden de fila mayor) de manera coherente; Para las matrices que exceden el tamaño de la memoria caché (pero cuyas filas pueden caber en la memoria caché), los datos deben leerse de la memoria dos veces y almacenarse una vez:
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;
}
}
}
La solución más simple que se me ocurre se pega a continuación. La lógica es registrar qué fila y columna establecer cero mientras itera.
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);
}
}
Aquí está mi implementación de Ruby con la prueba incluida, esto tomaría espacio O (MN). Si queremos una actualización en tiempo real (como mostrar los resultados cuando encontramos ceros en lugar de esperar el primer ciclo de encontrar ceros), podemos crear otra variable de clase como @output y siempre que encontremos un cero actualizamos @output y no @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
El siguiente código crea una matriz de tamaño m, n. Primero decida las dimensiones de la matriz. Quería llenar la matriz [m] [n] al azar con números entre 0..10. Luego cree otra matriz de las mismas dimensiones y llénela con -1s (matriz final). Luego, recorra la matriz inicial para ver si va a llegar a 0. Cuando llegue a la ubicación (x, y), vaya a la matriz final y llene la fila x con 0s y la columna y con 0s. Al final, lea la matriz final, si el valor es -1 (valor original) copie el valor en la misma ubicación de la matriz inicial a 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;
}
aquí está mi solución. Como puede ver en el código, dada una matriz M * N, establece toda la fila en cero una vez que inspecciona un cero en esa fila. La complejidad temporal de mi solución es O (M * N). Estoy compartiendo toda la clase que tiene una matriz poblada estática para probar y un método de matriz de visualización para ver el resultado en la consola.
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("");
}
}
}
One Pass: he recorrido la entrada solo una vez, pero he usado una nueva matriz y solo dos variables booleanas adicionales.
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();
}
