Defina todas as células da matriz como 0 se essa linha ou coluna contiver um 0

152

Dada uma matriz NxN com 0s e 1s. Defina todas as linhas que contêm a 0para todos os 0s e defina todas as colunas que contenham a 0para 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

resulta 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

Um engenheiro da Microsoft me disse que existe uma solução que não envolve memória extra, apenas duas variáveis ​​booleanas e uma passagem, por isso estou procurando por essa resposta.

BTW, imagine que seja uma matriz de bits, portanto, apenas 1s e 0s são permitidos na matriz.

jaircazarin-old-account
fonte
1
Hã? O que é "sempre que você encontrar"? Em que ordem você encontra os elementos na matriz? E se você encontrar todos os bits, você não receberá todos os 0s?
ShreevatsaR
Bem, a ordem na qual você decide encontrar os elementos é sua decisão, a coisa é que você deve definir apenas como 0 os elementos adequados. Se você encontrar todos os bits definidos como 0, sim, a matriz ainda será preenchida com zeros.
jaircazarin-old-account
O que são "os elementos adequados"? Você recebe duas matrizes, uma matriz "origem" e uma matriz "destino" e deve decidir em qual ordem "encontrar" os elementos para obter a matriz "destino"?
ShreevatsaR
1
Eu acho que você ouviu algo para o pensamento '1 passe'. Isso pode ser feito de forma linear em 2 passagens, porém, sem memória extra, a apenas 2 booleans ;-) Então eu assumir fortemente que é a solução que ele quis dizer (veja abaixo)
Piotr Lesnicki
1
Você pode verificar com seu amigo se a descrição do problema está realmente correta? Eu pensei que poderia fazer isso com códigos de Hamming ou bits de paridade, mas até agora não tive sucesso, e o problema continua na minha cabeça. :)
CSL

Respostas:

96

Ok, estou cansado porque são 3 da manhã aqui, mas tenho uma primeira tentativa com exatamente 2 passagens em cada número na matriz, então em O (NxN) e é linear no tamanho da matriz.

Eu uso a primeira coluna e a primeira linha como marcadores para saber onde estão as linhas / colunas com apenas 1. Então, existem 2 variáveis ​​le c para lembrar se a primeira linha / coluna também é 1. Portanto, o primeiro passe define os marcadores e redefine o restante para os zero.

A segunda passagem define 1 em locais onde as linhas e colunas foram marcadas como 1 e redefine a 1ª linha / coluna, dependendo de le c.

Duvido muito que possa ser feito em 1 passe, pois os quadrados no início dependem dos quadrados no final. Talvez meu segundo passe possa 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)
Piotr Lesnicki
fonte
Um problema aqui é se n> sizeof (c), então ele quebra. Para expandir isso para funcionar no caso geral de n, você precisaria dimensionar dinamicamente seu campo de bits, o que acho que violaria a restrição dada pelo problema.
Adam
Não, c não é um campo de bits, é apenas um bool. O & = não é um op bit a bit (bem, é, mas com um valor de 1 bit), está lá porque c informa se a primeira coluna é toda 1 (true) ou contém 0 (false).
Steve Jessop
2
Falha se a linha superior for [0,1,1,1 ...] Minha correção de erro é inicializar l para m [0] [0] em vez de 1
paperhorse
de fato l = 1 para i no intervalo (1, N): l & = m [0] [i] deve ser l = 1 para i no intervalo (N): l & = m [0] [i]
Kristof Neirynck
1
BTW, acredito que a condição na segunda passagem deve ser algo como: se m [i] [0] | m [0] [j]:
jaircazarin-old-account
16

Isso não pode ser feito em uma única passagem, pois um único bit afeta os bits antes e depois em qualquer ordem. IOW Qualquer que seja a ordem em que você atravessa a matriz, mais tarde você pode encontrar um 0, o que significa que você precisa voltar e alterar um 1 anterior para um 0.

Atualizar

As pessoas parecem pensar que, restringindo N a algum valor fixo (por exemplo, 8), você pode resolver esse é um passo. Bem, isso é a) não entender o assunto eb) não a questão original. Eu não postaria uma pergunta sobre classificação e esperaria uma resposta que começou "supondo que você queira classificar apenas 8 coisas ...".

Dito isto, é uma abordagem razoável se você souber que N é de fato restrito a 8. Minha resposta acima responde à pergunta original que não tem essa retribuição.

Draemon
fonte
Não pode ser feito de uma só vez sem memória adicional. Isso pode ser feito em uma passagem se houver outra matriz NxN para armazenar os resultados. Da mesma forma, com alguns ajustes de bits e duas passagens, isso pode ser feito sem memória adicional.
Paxos1977
2
Você ainda não pode fazer isso de uma só vez, mesmo que use uma matriz temporária, ou então há algo estranho que não estou conseguindo aqui. Você precisa de um passe para deduzir as informações da linha / coluna e um para definir tudo.
Lasse V. Karlsen
Resolvi esse problema reconhecendo que existe apenas um valor diferente de zero único por linha e apenas atribuindo-o por referência.
Daniel Papasian 08/12/08
@ceretullis, lassevk: Ainda acho que não pode ser feito de uma só vez. As passagens sobre essa segunda matriz teriam que contar - caso contrário, você poderá copiar a matriz em uma única passagem e trabalhar com a cópia da maneira que desejar. @ Daniel Papasian: Sua solução não escala, onde N> #bits em int / long / whatever
Draemon
Draemon, a técnica escala bem, é apenas matemática - você pode criar um hardware que faça isso ou pode usar técnicas de software para manipular números maiores que o tamanho da palavra. Nem viola as restrições do problema, IMHO
Daniel Papasian 08/12/08
10

Então, minha ideia é usar os valores na última linha / coluna como um sinalizador para indicar se todos os valores na coluna / linha correspondente são 1s.

Usando uma varredura em Zig Zag em toda a matriz, EXCETO a linha / coluna final. Em cada elemento, você define o valor na linha / coluna final como o AND lógico de si mesmo com o valor no elemento atual. Em outras palavras, se você acertar 0, a linha / coluna final será definida como 0. Se você for 1, o valor na linha / coluna final será 1 somente se já fosse 1. De qualquer forma, defina o elemento atual como 0.

Quando você terminar, sua linha / coluna final deverá ter 1s se a coluna / linha correspondente for preenchida com 1s.

Faça uma varredura linear na linha e coluna finais e procure por 1s. Defina 1s nos elementos correspondentes no corpo da matriz em que a linha e a coluna finais são 1s.

A codificação será complicada para evitar erros de um por um, etc., mas deve funcionar de uma só vez.

Alastair
fonte
Muito bom ... Eu estava pensando nas mesmas linhas, mas perdi o uso da linha / coluna final para armazenar essas informações, então fiquei com memória extra para um par de matrizes Nx1.
Dave Sherohman
1
Parece duas passagens para mim - uma delas é a verificação em zigue-zague, a segunda é o "Conjunto 1s nos elementos correspondentes no corpo da matriz, onde a linha e a coluna finais são ambas 1s".
Adam Rosenfield
A varredura em zigue-zague (que, como alguém me indicou, não é estritamente necessária) atravessa todos, mas a última linha / coluna. Portanto, a digitalização da coluna final / linha não duplica os elementos digitalizados anteriormente. Daí um passe. Em outras palavras, é O (N ^ 2) para uma matriz N * N.
Alastair
6

Eu tenho uma solução aqui, ela é executada em uma única passagem e faz todo o processamento "no local" sem memória extra (exceto para aumentar a pilha).

Ele usa recursão para atrasar a gravação de zeros, o que naturalmente destruiria a matriz para as outras linhas e colunas:

#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();
}
Adão
fonte
2
Solução agradável, mas você está, tecnicamente, usando mais memória do que os dois booleanos permitidos (embora na pilha).
csl
1
Isso é> 1 passe. Se você imprimir (rowIndex, i) e (i, colIndex) à medida que são acessados ​​em checkRow e checkCol, verá que cada elemento é acessado várias vezes.
314 Draemon
Draemon: Você está correto, acho que precisamos de uma definição clara de "passe único" do criador de charadas. Se ele realmente quer dizer que cada elemento pode ser acessado apenas uma vez, precisamos de uma solução diferente.
826 Adam
Imagino que o problema original (que chegou até nós através do jogo telefônico) significou que o problema deveria ser resolvido "no local", o que significa que você não tem outra cópia da matriz. E soluções mais ideais nem precisam de troca temporária () como armazenamento para processamento.
Adam
Também duvido que as restrições estejam se referindo ao código de máquina resultante. Ou seja, o "código" que forneci usa apenas 2 bools. Dependendo de quais otimizações meu compilador faz, tudo pode ser incorporado ou quem sabe o que mais. Acho que a minha solução é correta;)
Adam
4

Eu não acho que é factível. Quando você está no primeiro quadrado e seu valor é 1, não há como saber quais são os valores dos outros quadrados na mesma linha e coluna. Portanto, você deve verificar esses itens e, se houver um zero, retorne ao primeiro quadrado e altere seu valor para zero. Eu recomendo fazer isso em duas passagens - a primeira passagem reúne informações sobre quais linhas e colunas devem ser zeradas (as informações são armazenadas em uma matriz, por isso estamos usando memória extra). A segunda passagem altera os valores. Sei que essa não é a solução que você está procurando, mas acho que é prática. As restrições dadas por você tornam o problema insolúvel.

Boyan
fonte
Eu tenho quase a mesma solução (veja abaixo) sem matrizes adicionais. e é o tempo linear (2 passagens mas embora)
Piotr Lesnicki
@Piotr: Sim, a segunda passagem parece inevitável. A introdução de matrizes para armazenar as informações de linhas e colunas que propus torna o algoritmo mais direto e um pouco mais rápido, pois há menos verificação e alteração de valor. É uma troca entre armazenamento e eficiência.
Boyan
3

Eu posso fazer isso 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));
Eclipse
fonte
Isso é c #? O que significa ~?
Sker
É C ++. ~inverte todos os bits em uma variável. 0x00000000 passa a 0x00000000. Basicamente, começo com todos e limpo o bit para uma linha / coluna quando encontro um 0. CompleteCols possui os bits 2 e 3 configurados e CompleteRows possui os bits 2 e 4 configurados (com base em 0).
Eclipse em Eclipse
Depois, basta definir os bits na matriz correspondentes a um em CompleteCols e CompleteRows.
Eclipse em Eclipse
3

o problema pode ser resolvido de uma só vez

salvando a matriz em uma 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 .

agora imprima todos os valores como 0 para os valores de iej salvos em a e b, o restante dos valores é 1, isto é, (3,3) (3,4) (5,3) e (5,4)

Sidarta
fonte
1

Outra solução que leva duas passagens é acumular ANDs horizontal 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 poderia projetar esse algoritmo usando bits de paridade , códigos de Hamming ou programação dinâmica , possivelmente usando esses dois booleanos como um número de 2 bits, mas ainda não obtive sucesso.

Você pode verificar novamente a declaração do problema com seu engenheiro e nos informar? Se não é realmente uma solução, eu quero manter desbastando o problema.

csl
fonte
1

Mantenha uma única variável para acompanhar o que são todas as linhas AND juntas.

Se uma linha for -1 (todos os 1s), faça da próxima linha uma referência a essa variável

Se uma linha é qualquer coisa, mas é 0. Você pode fazer tudo de uma só vez. 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
     }
}

Isso deve ser feito em uma única passagem - mas há uma suposição aqui de que N é pequeno o suficiente para que a CPU faça aritmética em uma única linha; caso contrário, você precisará fazer um loop sobre cada linha para determinar se está tudo 1s ou não, acredito. Mas, como você está perguntando sobre algos e não restringindo meu hardware, eu começaria minha resposta com "Construa uma CPU que suporte aritmética de N bits ..."

Aqui está um exemplo de como isso pode ser feito em C. Observe que eu argumento que valores e arr juntos representam a matriz, e p e numproduct são meus iteradores e variáveis ​​de produto AND usados ​​para implementar o problema. (Eu poderia ter repetido arr com aritmética de ponteiro para validar 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 fornecidas.

Ou no PHP, se as pessoas pensam que meus jogos de pilha em C estão trapaceando (sugiro que não seja, porque devo poder armazenar a matriz da maneira que 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 esquecendo de algo?

Daniel Papasian
fonte
Isso não funciona se N for maior que o número de bits em um int / long / seja o que for, então eu acho que não conta.
314 Draemon
Ele também não capturará as coisas se os 0s estiverem na parte inferior da matriz (tente com valores [] = {-1, -9, -1, 14, -10}).
Eclipse
Draemon, especifiquei na minha resposta que, sem restrições de hardware como parte da pergunta, você começa com "Construir uma CPU que suporte aritmética de N bits".
Daniel Papasian 08/12/08
Josh, eu não sigo. Com a solução C ou PHP e a matriz que você sugeriu, recebo 6 0 6 0 0, que acredito ser a resposta correta.
Daniel Papasian 08/12/08
@ Daniel - Você não pode, porque N não é uma constante. Além de "construir um novo computador com palavras 1Mbit dificilmente é um passo algorítmica razoável.
Draemon
1

Belo desafio. Essa solução usa apenas dois booleanos criados na pilha, mas os booleanos são criados várias vezes na pilha, pois 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;
}

Isso digitaliza 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, em seguida, alterar os valores nesse padrão no retorno de cada uma das funções de varredura. (Debaixo para cima):

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

eaanon01
fonte
Eu acho que isso não está correto, pois você ainda usa muito mais do que dois booleanos na sua pilha.
csl 08/12/08
Como eu triste tipo de dois booleanos. É o mais próximo que consigo pensar das especificações que ele forneceu. Eu adoraria ver uma solução real aqui. Se é factível.
eaanon01
Não acho que os requisitos estejam se referindo ao crescimento da pilha. Eu acho que essa é uma solução perfeitamente válida.
088 Adam
Esse é o meu pensamento também. Mas não posso ter certeza até que alguém poste uma solução melhor. Pelo menos minha solução é compilável e pode ser verificada por qualquer pessoa. :) ... não encontrei código psudo para problemas práticos. Thnx
eaanon01
1

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.
  • funcionará para outros valores de N, mas 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;
    }
AnthonyLambert
fonte
É uma boa solução para ter certeza. E suponho que cada solução aqui negligencie pelo menos um dos requisitos. Então, ter uma solução com um valor permitido máximo para N não é a pior coisa do mundo, tão bom trabalho em um presente :)
Adam
Restringir N a 8 e reivindicar isso atende ao requisito de uma passagem é simplesmente burro. Esta não é uma solução geral. Nenhuma restrição do tamanho de N foi declarada na pergunta; portanto, você resolveu apenas um subproblema.
Draemon
mas todas essas soluções têm um limite em N de uma maneira ou de outra.
AnthonyLambert
Dizer que é uma passagem de N está obviamente completamente errado. Mesmo apenas lendo o valor de cada posição na matriz original é O (N ^ 2) e é definitivamente necessário ler o valor em cada posição pelo menos uma vez para poder calcular a solução. Mesmo que você armazene valores como bits únicos em um longo período, o acesso a cada bit será O (N ^ 2) porque existem O (N ^ 2) bits.
Alderath
É claramente uma passagem que o valor RowGrid armazena toda a grade e após a 1ª leitura seria um dos registradores do processador para todo o algoritmo, se o otimizador for bom.
AnthonyLambert
1

Na realidade. Se você deseja apenas executar o algoritmo e imprimir os resultados (ou seja, não restaurá-los, isso pode ser feito facilmente de uma só vez. O problema ocorre quando você tenta modificar a matriz enquanto executa o algoritmo.

Aqui está minha solução: envolve apenas ANDing dos valores de linhas / colunas para um elemento de givein (i, j) e imprimindo-o.

#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;
    }
}
Kenny Cason
fonte
1

Eu tentei resolver esse problema em c #.

Eu usei duas variáveis ​​de loop (iej) além da matriz real en representando sua dimensão

A lógica que tentei é:

  1. Calcular AND para linhas e colunas envolvidas em cada quadrado concêntrico da matriz
  2. Armazene-o em suas células de canto (eu as armazenei no sentido anti-horário)
  3. Duas variáveis ​​booleanas são usadas para reter valores de dois cantos ao avaliar um quadrado específico.
  4. Esse processo terminaria quando o loop externo (i) estivesse no meio do caminho.
  5. Avalie os resultados de outras células com base nas células de canto (no restante de i). Pule as células de canto durante esse processo.
  6. Quando eu atingir n, todas as células terão seu resultado, exceto as células de canto.
  7. Atualize as células de canto. Essa é uma iteração extra para o comprimento de n / 2, além da restrição de passagem única mencionada 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;
            }
        }
    }
}
BK
fonte
1

Uma passagem - eu percorri a entrada apenas uma vez, mas usei 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();

    }
RahulDeep Attri
fonte
0

Embora impossível, dadas as restrições, a maneira mais eficiente em termos de espaço é atravessar a matriz de maneira alternada de linha / coluna, sobrepostas, o que criaria um padrão semelhante ao assentamento de tijolos em zigue-zague:

-----
|----
||---
|||--
||||-

Usando isso, você entraria em cada linha / coluna, conforme indicado, e se encontrar um 0 a qualquer momento, defina uma variável booleana e ande novamente nessa linha / coluna, definindo as entradas como 0 à medida que avança.

Isso não exigirá memória extra e usará apenas uma variável booleana. Infelizmente, se a borda "distante" estiver definida como 0, esse é o pior caso e você percorrerá toda a matriz duas vezes.

cdeszaq
fonte
Eu posso estar errado, mas você tem certeza que isso funciona? Quando você está na terceira coluna, digamos, como você sabe se o valor na parte superior dela, na primeira linha, era 1 ou 0 antes de processar a primeira linha?
9603 Steve Jessop #
Você não sabe, mas também não precisa. Se fosse um 0, a coluna inteira precisará ser 0. Se o valor na linha anterior for 1, você saberá que todas as linhas acima dela são 1 (e sempre foram).
Dave Sherohman
0

crie uma matriz de resultados e defina todos os valores como 1. passe pela matriz de dados assim que um 0 for encontrado, defina a coluna da linha da matriz de resultados como 0

No final da primeira passagem, a matriz de resultados terá a resposta correta.

Parece bem simples. Há um truque que estou perdendo? Você não tem permissão para usar um conjunto de resultados?

EDITAR:

Parece uma função F #, mas isso está enganando um pouco, pois mesmo que você esteja executando uma única passagem, a função pode ser recursiva.

Parece que o entrevistador está tentando descobrir se você conhece programação funcional.

mson
fonte
1
Usar um conjunto de resultados consumiria memória extra.
Cdeszaq 04/04/08
A programação funcional não modifica a matriz original no local.
Svante
0

Bem, eu vim com uma solução de passagem única no local (não recursiva) usando 4 bools e 2 contadores de loop. Não consegui reduzi-lo para 2 bools e 2 ints, mas não ficaria surpreso se fosse possível. Faz cerca de 3 leituras e 3 gravações de cada célula, e deve ser O (N ^ 2), ie. linear no tamanho da matriz.

Demorei algumas horas para resolver este problema - eu não gostaria de ter que pensar nisso sob a pressão de uma entrevista! Se eu fiz um booboo, estou cansado demais para vê-lo ...

Hum ... estou escolhendo definir "passagem única" como fazer uma varredura pela matriz, em vez de tocar em 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;
}

fonte
0

Espero que você goste da minha solução c # de 1 passagem

você pode recuperar um elemento com O (1) e precisa apenas do 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
*/
usuario
fonte
Acho que o único problema pode ser que você esteja usando duas matrizes extras de dados para fazer isso funcionar. Uma das estipulações é não usar memória extra. Mas bom! isso é basicamente o que eu fiz na minha resposta :)
Kenny Cason
0

1 passe, 2 booleanos. Eu só tenho que assumir que os índices inteiros nas iterações não contam.

Esta não é uma solução completa, mas não consigo passar neste ponto.

Se eu pudesse determinar se um 0 é um 0 original ou um 1 que foi convertido em um 0, não precisaria usar -1 e isso funcionaria.

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 é usar a primeira metade do exame de uma linha ou coluna para determinar se ela contém 0 e a última metade para definir os valores - isso é feito observando xe largura-xe depois y e altura -y em cada iteração. Com base nos resultados da primeira metade da iteração, se um 0 na linha ou coluna foi encontrado, eu uso a última metade da iteração para alterar os 1s para -1s.

Acabei de perceber que isso poderia ser feito com apenas 1 booleano deixando 1 para ...?

Estou postando isso esperando que alguém possa dizer: "Ah, faça isso ..." (E eu gastei muito tempo para não postar).

Aqui está o código no 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
rvarcher
fonte
0

Ninguém está usando formulários binários? como são 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
KFL
fonte
0

Você pode fazer algo assim para usar uma passagem, mas uma matriz de entrada e saída:

output(x,y) = col(xy) & row(xy) == 2^n

onde col(xy)estão os bits na coluna que contém o ponto xy; row(xy)são os bits na linha que contêm o ponto xy. né o tamanho da matriz.

Em seguida, basta fazer um loop sobre a entrada. Possivelmente expansível para ser mais eficiente em termos de espaço?

Warbum
fonte
0

Uma varredura matricial, dois booleanos, sem recursão.

Como evitar o segundo passe? A segunda passagem é necessária para limpar as linhas ou colunas quando o zero aparecer no final.

No entanto, esse problema pode ser resolvido porque, quando examinamos a linha #i, já sabemos o status da linha # i-1. Portanto, enquanto estivermos varrendo a linha #i, podemos limpar simultaneamente a linha # i-1, se necessário.

A mesma solução funciona para colunas, mas precisamos varrer linhas e colunas simultaneamente enquanto os dados não são alterados na próxima iteração.

Dois booleanos são necessários para armazenar o status da primeira linha e da primeira coluna, porque seus valores serão alterados durante a execução da parte principal do algoritmo.

Para evitar adicionar mais booleanos, estamos armazenando o sinalizador "clear" 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();
}
Artemix
fonte
0

parece que o seguinte funciona sem requisitos adicionais de espaço:

primeira nota que multiplicar os elementos da linha vezes os elementos da linha em que um elemento está, fornece o valor desejado.

Para não usar espaço adicional (não criando uma nova matriz e preenchendo-a, mas aplicando alterações diretamente na matriz), inicie o canto superior esquerdo da matriz e faça o cálculo para qualquer matriz ixi (que "começa" em (0 , 0)) antes de considerar qualquer elemento com qualquer índice> i.

espero que isso funcione (havent testet)

DFF
fonte
Parece estar incorreto. Suponha que a linha 0 tenha apenas 1 valores. Se o valor final definido para (0,0) for 0, mais tarde você definirá a linha completa como 0, o que não é necessariamente correto. Você realmente precisa armazenar 2 valores por célula para fazer o estilo de programação dinâmica, usando seu princípio.
Eyal Schneider
claro, você está certo. Em vez de armazenar dois valores, eu também poderia usar uma terceira posibilidade, digamos -1, que significa células que são 1 na matriz "antiga" que eventualmente serão substituídas por um 0. Claro, dessa forma, é preciso ter absoluta certeza. valores após multiplicações. No final, todos os -1 são substituídos por 0.
DFF
0

Esta é TESTADO para N diferente em C ++, e é:
One Pass , DOIS BOOLS , NO RECURSÃO , NO memória extra , vale para ARBITRARLY GRANDE N
(Até agora, nenhuma das soluções aqui fazer tudo isso.)

Mais especificamente, estou divertido dois contadores de loop estão bem. Eu tenho duas const assinadas, que existem apenas ao invés de serem computadas todas as vezes para facilitar a leitura. O intervalo do loop externo é [0, N] e o intervalo do loop interno é [1, n - 1]. A declaração switch está no loop principalmente para mostrar muito claramente que é realmente apenas uma passagem.

Estratégia de algoritmo:

O primeiro truque é para nós uma linha e uma coluna da própria matriz para acumular o conteúdo da matriz; essa memória fica disponível ao descarregar tudo o que realmente precisamos saber da primeira linha e coluna em dois booleanos. O segundo truque é obter duas passagens de uma, usando a simetria da sub-matriz e seus índices.

Sinopse do algoritmo:

  • Digitalize a primeira linha e armazene se todas elas estão em um booleano; faça o mesmo para a primeira coluna que armazena o resultado em um segundo booleano.
  • Para a sub-matriz, excluindo a primeira linha e a primeira coluna: percorra, da esquerda para a direita, de cima para baixo, como se lê um parágrafo. Ao visitar cada elemento, também visite o elemento correspondente que seria visitado se visitar a sub-matriz ao contrário. Para cada elemento visitado E seu valor para onde sua linha cruza a primeira coluna e também AND seu valor para onde sua coluna cruza a primeira linha.
  • Quando o centro da sub-matriz for alcançado, continue visitando os dois elementos simultaneamente, como acima. No entanto, agora defina o valor dos elementos visitados como AND de onde sua linha cruza a primeira coluna e de onde sua coluna cruza a primeira linha. Depois disso, a sub-matriz está completa.
  • Use as duas variáveis ​​booleanas calculadas no início para definir a primeira linha e a primeira coluna com seus valores corretos.

Implementação C ++ modelo:

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;
}
A priori
fonte
0

Ok, percebo que não é exatamente uma correspondência, mas consegui de uma só vez usando um bool e um byte em vez de dois bools ... perto. Eu também não atestaria a eficiência, mas esses tipos de perguntas geralmente exigem soluções abaixo do ideal.

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; }
        }
    }
}
Walery Strauch
fonte
0

Você pode fazer isso de uma só vez - se não contar acessando a matriz em ordem de acesso aleatório, o que elimina os benefícios de fazer uma única passagem em primeiro lugar (coerência de cache / largura de banda de memória).

[editar: solução simples, mas errada, excluída]

Você deve obter um desempenho melhor do que qualquer método de passagem única, fazendo-o em duas passagens: uma para acumular informações de linha / coluna e outra para aplicá-las. A matriz (na ordem principal da linha) é acessada de forma coerente; para matrizes que excedem o tamanho do cache (mas cujas linhas podem caber no cache), os dados devem ser lidos na 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;
        }
    }
}
tempestade
fonte
0

A solução mais simples que consigo pensar é colada abaixo. A lógica é registrar qual linha e coluna definir zero durante 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);
    }
}
geekprogrammer
fonte
0

Aqui está minha implementação do Ruby com o teste incluído. Isso ocuparia espaço O (MN). Se queremos uma atualização em tempo real (gostamos de 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 @outpute sempre que encontrarmos um zero, atualizamos @outpute 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
Eki Eqbal
fonte
0

O código abaixo cria uma matriz de tamanho m, n. Primeiro decida as dimensões da matriz. Eu queria preencher a matriz [m] [n] aleatoriamente com números entre 0..10. Em seguida, crie outra matriz das mesmas dimensões e preencha-a com -1s (matriz final). Em seguida, percorra a matriz inicial para ver se você atingirá 0. Quando você atingir o local (x, y), vá para a matriz final e preencha a linha x com 0s e a coluna y com 0s. No final, leia a matriz final, se o valor for -1 (valor original), copie o valor no mesmo local da matriz inicial para 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;
}
user3743369
fonte
Você não fornece nenhuma explicação ou contexto para o código publicado.
Aaron
Espero que seja melhor agora. Obrigado pelo aviso. Eu gostaria de explicar mais, se não estiver claro para você.
precisa saber é o seguinte
0

aqui está a minha solução. Como você pode ver no código, dada uma matriz M * N, ela define a linha inteira como zero quando inspeciona um zero nessa linha. A complexidade de tempo da minha solução é O (M * N). Estou compartilhando toda a classe que possui uma matriz preenchida estática para teste e um método de matriz de exibição 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("");
    }

}

}

Türkmen Mustafa Demirci
fonte