Definir cada célula da matriz a 0, se essa linha ou coluna contém um 0
https://stackoverflow.com/questions/339262
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Dada uma matriz NxN com 0s e 1s. Definir cada linha que contém uma 0 a todos os 0s e definir cada coluna que contém uma 0 a todos os 0s.
Por exemplo
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
resultado em
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
A Microsoft engenheiro me disse que não é uma solução que não envolve memória extra, apenas duas variáveis ??booleanas e uma passagem, então eu estou procurando a resposta.
BTW, imagino que é uma matriz bit, portanto, apenas 1s e 0s são permitir para ser na matriz.
Solução
Ok, então eu estou cansado, pois de três horas aqui, mas eu tenho uma primeira inplace tentativa com exatamente 2 passes em cada número na matriz, assim, em O (NxN) e é linear no tamanho da matriz.
Eu uso coluna 1º e primeira linha como marcadores de saber onde estão linhas / cols com apenas 1 de. Então, existem 2 variáveis ??L e C para se lembrar se fileira 1º / coluna são todos 1s também. Então, a primeira passagem define os marcadores e redefine o resto a 0 do.
O segundo conjuntos de passe 1 em lugares onde as linhas e cols onde marcado para ser 1, e redefinições 1ª linha / col dependendo l e c.
duvido muito que eu possa ser feito em 1 passagem como quadrados no início dependem quadrados no final. Talvez a minha segunda passagem pode ser mais 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)
Outras dicas
Isto não pode ser feito em uma passagem já que um único bit tem um efeito sobre os bits antes e depois de qualquer encomenda. fim IOW Tudo o que você percorrer a matriz, você pode mais tarde vêm em um 0 que significa que você tem que voltar atrás e mudar uma anterior 1 para 0.
Atualização
As pessoas parecem pensar que restringindo N para algum valor fixo (digamos 8) você pode resolver isso é uma passagem. Bem, isso é a) faltando o ponto e b) não a pergunta original. Eu não ia postar uma pergunta sobre a classificação e esperar uma resposta que começou "supondo que você só quer classificar 8 coisas ...".
Dito isto, é uma abordagem razoável se você sabe que N é de fato restrito a 8. A minha resposta acima respostas à pergunta original, que não tem tal retriction.
Assim, a minha idéia é usar os valores na última linha / coluna como uma bandeira para indicar se todos os valores na correspondente coluna / linha são 1s.
Usando um Zig Zag varredura através de toda a matriz EXCETO a linha / coluna final. Em cada elemento, você definir o valor na linha / coluna final quanto à lógica e de si mesmo com o valor no elemento atual. Em outras palavras, se você bater um 0, a linha / coluna final será definido como 0. Se você que um 1, o valor na linha / coluna final será 1 apenas se foi 1 já. Em qualquer caso, definir o elemento atual para 0.
Quando você terminar, a sua linha final / coluna deve ter 1s sse o correspondente coluna / linha estava cheio de 1s.
Do linear de digitalização através da linha final e coluna e à procura de 1s. Conjunto 1s nos elementos correspondentes no corpo da matriz, onde a última fila e coluna são ambos 1s.
Codificação vai ser complicado para evitar off-by-one erros etc, mas ele deve funcionar em uma passagem.
Eu tenho uma solução aqui, ele é executado em uma única passagem, e faz todo o processamento "in place" sem memória extra (excepto para o crescimento da pilha).
Ele usa recursão para atrasar a escrita de zeros que naturalmente iria destruir a matriz para as outras linhas e 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();
}
Eu não acho que é factível. Quando você está na primeira casa e seu valor é 1, você não tem como saber o que os valores das outras praças na mesma linha e coluna são. Então, você tem que verificar os e se há um zero, retorno para a primeira praça e altere seu valor para zero. Vou recomendar a fazê-lo em duas passagens - a primeira informação reúne passa sobre quais linhas e colunas devem ser zerado (as informações são armazenadas em uma matriz, por isso estamos usando alguma memória extra). A segunda passagem muda os valores. Eu sei que não é a solução que você está procurando, mas eu acho que é uma prática. As restrições dadas por você tornar o problema insolúvel.
Eu posso fazê-lo com duas variáveis ??inteiras e duas passagens (até 32 linhas e colunas ...)
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));
o problema pode ser resolvido em um passe
poupar a matriz em uma matriz X j i.
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 .
Agora imprimir todos os valores como 0 para valores de i e j salvos em um e b restantes valores são um ou seja, (3,3) (3,4) (5,3) e (5,4)
Outra solução que leva duas passagens, é acumular ANDs horizontalmente e 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
Eu pensei que eu poderia projetar um algoritmo tal usando bits de paridade , códigos de Hamming ou dinâmica de programação , possivelmente usando esses dois booleans como um número de 2-bit, mas eu não teve sucesso ainda.
Você pode por favor re-verificar a declaração do problema com o seu engenheiro e deixe-nos saber? E se há é realmente uma solução, eu quero manter desbastando o problema.
Mantenha uma única variável para manter o controle do que todas as linhas ANDed juntos são.
Se uma linha é -1 (1s), em seguida, fazer a próxima fileira uma referência a essa variável
Se uma linha não é nada, é um 0. Você pode fazer tudo em uma passagem. Pseudo-código:
foreach (my $row) rows {
$andproduct = $andproduct & $row;
if($row != -1) {
zero out the row
} else {
replace row with a reference to andproduct
}
}
Isso deve fazê-lo, em uma única passagem - mas há um pressuposto aqui que N é pequeno o suficiente para a CPU para fazer aritmética em uma única linha, então você está indo para necessidade de loop sobre cada linha para determinar se é todos os 1s ou não, eu acredito. Mas, dado que você está perguntando sobre algos e não constranger o meu hardware, eu só iria começar a minha resposta com "Construir uma CPU que suporta N-bit aritmética ..."
Aqui está um exemplo de como isso pode ser feito em C. Nota I argumentam que os valores e arr tomados em conjunto representam a matriz, e p e numproduct é meu iterador e e variáveis ??produto usar para implementar o problema. (Eu poderia ter loop sobre arr com aritmética de ponteiro para validar o meu trabalho, mas já foi o 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;
}
Isso produz 0, 0, 6, 0, 6, que é o resultado para as entradas dadas.
Ou em PHP, se as pessoas pensam meus jogos pilha em C estão enganando (sugiro a você que não é, porque eu deveria ser capaz de armazenar a matriz do jeito que eu quiser):
<?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);
Estou faltando alguma coisa?
challange Nice. Este tipo solução de usos apenas dois booleans criados na pilha, mas os booleans são criadas várias vezes na pilha uma vez que a função é 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;
}
Este scans em um padrão 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
e assim por diante
E então changeing os valores neste padrão no retorno sobre cada uma das funções de digitalização. (Bottom up):
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
e assim por diante
Ok esta é uma solução que
- usa apenas um valor extra longo para armazenamento de trabalho.
- não usa recursão.
- uma passagem de apenas N, nem mesmo N * N.
- irá trabalhar para outros valores de N, mas vai precisar de novos #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;
}
Na verdade. Se você quiser apenas para executar o algoritmo e imprimir os resultados (ou seja, não restaurá-los, então isso pode ser feito facilmente em uma passagem. O problema surge quando você tentar modificar a matriz como você está executando o algoritmo.
Aqui está a minha solução que envolve apenas Anding os / valores Linhas Colunas para uma givein (i, j) do elemento e imprimi-lo.
#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;
}
}
Eu tentei resolver este problema em C #.
eu usei duas variáveis ??de laço (i e j) para além da matriz real e n representando a sua dimensão
Logic eu tentei é:
- calcular e para linhas e cols envolvidos em cada quadrado concêntrico da matriz
- armazená-lo em suas células de canto (que eu armazenados-los em ordem anti-horário)
- variáveis ??Dois bool são usados ??para manter os valores de dois cantos quando se avalia um quadrado particular.
- Este processo termina quando loop externo (i) é meio caminho.
- Avaliar os resultados de outras células com base nas células de canto (para resto i). Passar as células de canto durante este processo.
- Quando eu atinge n, todas as células teria o seu resultado, exceto para as células de canto.
- Atualize as células esquina. Esta é uma iteração adicional ao comprimento de N / 2 do que a outra restrição único passe mencionado no 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;
}
}
}
}
Enquanto impossível dadas as limitações, a forma mais eficiente do espaço de fazer isso é por que atravessa a matriz numa overlaping, alternando moda linha / coluna, o que tornaria um padrão similar aos tijolos que colocam na forma de zig-zag:
-----
|----
||---
|||--
||||-
Usando isso, você iria em cada linha / coluna, como indicado, e se você encontrar um 0 a qualquer momento, definir uma variável boolean, e re-caminhar nessa linha / coluna, definindo as entradas para 0 como você ir .
Isso vai exigir nenhuma memória extra, e só vai usar uma variável booleana. Infelizmente, se a borda "agora" está definido para todos ser 0, que é o pior caso e você anda toda a série duas vezes.
criar uma matriz de resultados e definir todos os valores para 1. atravessar a matriz de dados assim que um 0 é encontrado, defina a coluna de linha da matriz resultado para 0
No final da primeira passagem, a matriz resultado terá a resposta correta.
Parece muito simples. Existe um truque que eu estou ausente? você não tem permissão para usar um conjunto de resultados?
EDIT:
Looks como uma função F #, mas isso é batota um pouco desde que mesmo que você está fazendo uma única passagem, a função pode ser recursiva.
Parece que o entrevistador está tentando descobrir se você sabe de programação funcional.
Bem, eu vim com uma única passagem, a solução no local (não-recursiva), utilizando 4 bools e 2 contadores de loop. Eu não conseguiram reduzi-la a 2 bools e 2 ints, mas eu não ficaria surpreso se fosse possível. Ele faz cerca de 3 lê e escreve 3 de cada célula, e que deveria ser O (N ^ 2), isto é. linear no tamanho da matriz.
Levou-me um par de horas para confundir um presente para fora - Eu não quero ter que vir para cima com ele sob a pressão de uma entrevista! Se eu fiz um booboo Estou cansado demais para detectá-lo ...
Um ... Eu estou escolhendo para definir "single-pass" como fazer uma varredura através da matriz, em vez de tocar cada valor uma 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;
}
i esperamos que você aproveite a minha solução c # 1-pass
Você pode recuperar um elemento com O (1) e apenas necessidade o espaço de uma linha e uma coluna da 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 passe, 2 booleans. Eu só tenho que assumir os índices inteiros nas iterações não contam.
Esta não é uma solução completa, mas eu não consigo me passar este ponto.
Se eu pudesse determinar se um 0 é um original 0 ou um 1, que foi convertido para um 0, então eu não teria que usar -1 e este iria funcionar.
A minha saída é assim:
-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
A originalidade da minha abordagem está usando a primeira metade do exame de uma linha ou coluna para determinar se ele contém um 0 e a última metade para definir os valores - isto é feito por olhar para x e largura-x e, em seguida, y e y-altura em cada iteração. Com base nos resultados da primeira metade da iteração, se um 0 na linha ou coluna foi encontrado, que use a última metade da iteração para alterar as 1s a -1 de.
Eu só percebi isso poderia ser feito com apenas 1 boolean deixando 1 a ...?
Vou colocar esta esperando que alguém poderia dizer: "Ah, basta fazer isso ..." (E eu passei tempo demais sobre ele não post.)
Aqui está o código em 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
Ninguém está usando formas binárias? uma vez que é apenas 1 e 0. Podemos usar vetores binários.
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
Aqui está o teste:
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)
E a saída:
Before...
10110
01110
11111
10111
11111
After...
00000
00000
00110
00000
00110
Você pode fazer algo como isto para usar uma passagem, mas uma matriz de entrada e saída:
output(x,y) = col(xy) & row(xy) == 2^n
onde é col(xy) os bits na coluna contendo o xy ponto; row(xy) é os bits na linha que contém a xy ponto. n é o tamanho da matriz.
Em seguida, basta loop sobre a entrada. Possivelmente expansível para ser mais eficiente do espaço?
Uma varredura matriz, duas booleans, sem recursão.
Como evitar a segunda passagem? A segunda passagem é necessária para limpar as linhas ou colunas quando os appeares zero no seu fim.
No entanto, este problema pode ser resolvido, porque quando nós fazemos a varredura linha #i já sabemos o status de linha para a linha # i-1. Então, enquanto estamos a digitalizar o #i linha que pode, simultaneamente, limpar a linha # i-1 se for necessário.
A mesma solução funciona para colunas, mas precisamos de linhas e colunas de varredura simultaneamente, enquanto os dados não são alterados pela próxima iteração.
Dois booleans são necessários para armazenar o status de primeira linha e primeira coluna, porque seus valores serão alterados durante a execução da parte principal do algoritmo.
Para evitar a adição de mais booleans estamos armazenando a bandeira "claro" para as linhas e colunas na primeira linha e coluna da 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 os seguintes trabalhos sem exigências de espaço adicional:
primeira nota que multiplicando os elementos das vezes os elementos de linha da linha em que um elemento é, dá o valor desejado.
A fim de não usar qualquer espaço adicional (não fazer uma nova matriz e preenchê-lo, mas sim aplicar as alterações para a matriz diretamente), começa a parte superior esquerda da matriz e fazer o cálculo para quaisquer ixi matriz (que "começa" em (0,0)) antes de considerar qualquer elemento com qualquer índice> i.
espero que isso funcione (havent testet)
Esta é TESTADO N diferente em C ++, e é:
One Pass , DOIS BOOLS , NÃO RECURSÃO , NÃO memória extra , vale para n ARBITRARLY GRANDE
(Até agora, nenhuma das soluções aqui fazer tudo isso.)
Mais especificamente, estou divertem dois contadores de loop estão bem. Eu tenho dois unsigneds const, que só existem em vez de ser calculado cada vez para facilitar a leitura. O intervalo do circuito externo é [0, N], e o intervalo do ciclo interior é [1, n - 1]. A instrução switch é no circuito existe principalmente para mostrar muito claramente que é realmente apenas uma passagem.
Estratégia Algoritmo:
O primeiro truque é para nós uma linha e uma coluna a partir da própria matriz para acumular o conteúdo da matriz, esta memória se torna disponível, transferindo tudo o que realmente precisa saber a partir da primeira linha e coluna em duas booleans. O segundo truque é fazer dois passes para fora de um, usando a simetria da sub-matriz e seus índices.
Algoritmo Sinopse:
- Digitalizar a primeira linha e loja se eles são todos aqueles em um boolean, fazer o mesmo para a primeira coluna armazenando o resultado em uma segunda boolean.
- Para o sub-matriz excluindo a primeira linha e a primeira coluna: iterate através, esquerda para a direita, de cima para baixo, como seria de ler um parágrafo. Ao visitar cada elemento, também visitar o elemento correspondente que seria visitada se visitar a sub-matriz em sentido inverso. Para cada elemento visitou e seu valor para o qual sua linha cruza a primeira coluna, e também e seu valor para onde a sua coluna atravessa a primeira linha.
- Uma vez que o centro do sub-matriz é atingido, continuar para visitar os dois elementos, simultaneamente, como acima. No entanto, agora definir o valor dos elementos visitados para o E de onde sua linha cruza a primeira coluna, e de onde a sua coluna atravessa a primeira linha. Depois disso, a sub-matriz está completa.
- Use as duas variáveis ??booleanas calculados à implorando para definir a primeira linha e a primeira coluna com os valores corretos.
Implementação templatized C ++:
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, eu percebo que não é um bom jogo, mas consegui-lo em uma passagem usando um bool e um byte em vez de duas bools ... perto. Eu também não iria atestar a eficiência do mesmo, mas esses tipos de perguntas, muitas vezes exigem menos de soluções ó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; }
}
}
}
Você pode sorta fazê-lo em uma passagem - se você não contar o acesso a matriz, a fim de acesso aleatório, o que elimina os benefícios de fazê-lo single-pass, em primeiro lugar (cache-coerência / memória de largura de banda ).
[edit: simples, mas solução errada suprimido]
Você deve obter um melhor desempenho do que qualquer método de passagem única por fazê-lo em duas passagens: um para acumular informações linha / coluna, e um para aplicá-la. A matriz (em ordem da maior linha) é acedido de forma coerente; para matrizes que excedam o tamanho do cache (mas cujas linhas podem caber no cache), os dados devem ser lidos a partir da memória duas vezes, e armazenados uma 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;
}
}
}
A solução mais simples que posso pensar é colado abaixo. A lógica é a de registro que linha e coluna para conjunto de zero, enquanto a iteração.
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);
}
}
Aqui está minha implementação de Ruby com o teste incluído, isso levaria O (MN) espaço. Se queremos uma atualização em tempo real (como para mostrar os resultados quando encontramos zeros em vez de esperar o primeiro ciclo de encontrar zeros) podemos apenas criar outra variável de classe como @output e sempre que encontrar um zero update que @output e não @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
O código abaixo cria uma matriz de tamanho m, n. Primeiro decidir as dimensões da matriz. Eu queria encher a matriz [m] [n] com aleatoriamente com números entre 0..10. Em seguida, criar uma outra matriz com as mesmas dimensões e preenchê-lo com -1s (matriz final). Em seguida, percorrer a matriz inicial para ver se você vai bater 0. Quando você bate no local (x, y), vá para a matriz final e preencher a linha x com 0s e coluna y com 0s. No final lido através da matriz final, se o valor for -1 (valor original) copiar o valor na mesma localização da matriz inicial para 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;
}
aqui é a minha solução. Como você pode ver a partir do código, dada uma matriz M * N, ele define a linha inteira de zero, uma vez que inspeciona um zero em que a complexidade do tempo row.the da minha solução é O (M * N). Eu estou compartilhando toda a classe que tem uma matriz preenchida estática para testar e um método de matriz de vídeo para ver o resultado no 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("");
}
}
}
One Pass -. Tenho atravessado a entrada apenas uma vez, mas usou uma nova matriz e apenas duas variáveis ??booleanas extras
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();
}
