Ustaw każdą komórkę w macierzy na 0, jeśli ten wiersz lub kolumna zawiera 0

Nie można tego zrobić w jednym przejściu, ponieważ pojedynczy bit ma wpływ na bity przed i po nim w dowolnej kolejności. Niezależnie od tego, w jakiej kolejności przemierzasz tablicę, możesz później przejść przez 0, co oznacza, że musisz cofnąć się i zmienić poprzednie 1 na 0.

Update

Ludzie wydają się myśleć, że ograniczając N do jakiejś stałej wartości (powiedzmy 8) można rozwiązać to jest jeden pass. Cóż, to jest a) brakuje punktu i b) nie oryginalne pytanie. Nie pisałbym pytania na sortowanie i oczekuj odpowiedzi, która zaczęła się "zakładając, że chcesz sortować tylko 8 rzeczy...".

To powiedziawszy, jest to rozsądne podejście, jeśli wiesz, że N jest w rzeczywistości ograniczone do 8. Moja powyższa odpowiedź odpowiada na pierwotne pytanie, które nie ma takiej retrykcji.

Więc moim pomysłem jest użycie wartości w ostatnim wierszu / kolumnie jako flagi, aby wskazać, czy wszystkie wartości w odpowiedniej kolumnie / wierszu są 1s.

Za pomocą Zig Zag scan przez całą macierz z wyjątkiem ostatniego wiersza/kolumny. W każdym elemencie ustawia się wartość w ostatnim wierszu / kolumnie jako logiczną i samą z wartością w bieżącym elemencie. Innymi słowy, jeśli trafisz 0, ostatni wiersz / kolumna zostanie ustawiona na 0. Jeśli to 1, wartość w ostatnim wierszu / kolumnie będzie 1 tylko jeśli już było 1. W każdym przypadku Ustaw bieżący element na 0.

Kiedy skończysz, twój ostatni wiersz / kolumna powinna mieć 1s iff odpowiednia kolumna / wiersz został wypełniony 1s.

Wykonaj skanowanie liniowe przez ostatni wiersz i kolumnę i poszukaj 1s. Ustaw 1s w odpowiednich elementach w ciele macierzy, gdzie ostatni wiersz i Kolumna są zarówno 1s.

Kodowanie będzie trudne, aby uniknąć błędów off-by-one itp., ale powinno działać w jednym przejściu.

Mam tutaj rozwiązanie, działa w jednym przejściu i robi wszystkie przetwarzanie "na miejscu" bez dodatkowej pamięci (z wyjątkiem powiększania stosu).

Używa rekurencji, aby opóźnić pisanie zer, które oczywiście zniszczyłyby macierz dla pozostałych wierszy i 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();
}

To chyba nie da się zrobić. Gdy znajdujesz się na pierwszym kwadracie i jego wartością jest 1, nie masz możliwości poznania wartości pozostałych kwadratów w tym samym wierszu i kolumnie. Więc musisz je sprawdzić i jeśli jest zero, wróć do pierwszego kwadratu i zmień jego wartość na zero. Polecam zrobić to w dwóch passach - pierwszy pass zbiera informacje o tym, które wiersze i kolumny muszą zostać wyzerowane (informacje są przechowywane w tablicy, więc używamy dodatkowej pamięci). Drugi pass zmienia wartości. Wiem, że nie jest to rozwiązanie, którego szukasz, ale myślę, że jest praktyczne. Podane przez Ciebie ograniczenia sprawiają, że problem jest nierozwiązywalny.

Mogę to zrobić za pomocą dwóch zmiennych całkowitych i dwóch przejść (do 32 wierszy i kolumn...)

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));

Problem można rozwiązać jednym przejściem

Zapisanie macierzy w tablicy 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 .

Teraz wypisuje wszystkie wartości jako 0 dla wartości i I j zapisanych w a i b pozostałe wartości to 1 ie (3,3) (3,4) (5,3) i (5,4)

innym rozwiązaniem , które zajmuje dwa przejścia, jest gromadzenie IDS poziomo i pionowo:

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    

Myślałem, że mogę zaprojektować taki algorytm używając bitów parzystości, Hamming codes lub dynamic programming , prawdopodobnie używając tych dwóch booleanów jako liczby 2-bitowej, ale nie odniosłem jeszcze sukcesu.

Czy możesz ponownie sprawdzić Oświadczenie o problemie ze swoim inżynierem i dać nam znać? Jeśli istnieje jest rzeczywiście rozwiązanie, chcę nadal chipping z dala od problemu.

Zachowaj pojedynczą zmienną, aby śledzić, co wszystkie wiersze i razem są.

Jeśli wiersz ma wartość -1 (wszystkie 1s), to w następnym wierszu należy umieścić odniesienie do tej zmiennej

Jeśli wiersz jest cokolwiek, ale, to jest 0. Możesz zrobić wszystko za jednym razem. Psuedo-kod:

foreach (my $row) rows {
     $andproduct = $andproduct & $row;
     if($row != -1) {
        zero out the row
     }  else {
        replace row with a reference to andproduct
     }
}

To powinno wystarczyć, w jednym przejściu -- ale istnieje tutaj założenie, że N jest wystarczająco małe, aby procesor wykonywał arytmetykę w jednym wierszu, w przeciwnym razie będziesz musiał zapętlić każdy wiersz, aby określić, czy to wszystko 1s lub nie, jak sądzę. Ale biorąc pod uwagę, że pytasz o algos i nie ograniczasz mojego sprzętu, po prostu zacznę moją odpowiedź od " Zbuduj procesor, który obsługuje arytmetykę N-bitową..."

Oto jeden przykład, jak można to zrobić w C. Uwaga twierdzę, że wartości i arr wzięte razem reprezentują tablicę, a p i numproduct są moim iteratorem i zmiennymi produktu używanymi do implementacji problemu. (Mogłem zapętlić arr arytmetyką wskaźnikową, aby zweryfikować moją pracę, ale kiedyś był wystarczy!)

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;
}

To daje 0, 0, 6, 0, 6, co jest wynikiem dla danych wejść.

Lub w PHP, jeśli ludzie myślą, że moje gry w C oszukują (sugeruję ci, że tak nie jest, ponieważ powinienem być w stanie przechowywać matrycę w dowolny sposób):

<?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);

Niezłe wyzwanie. To rozwiązanie wykorzystuje tylko dwie wartości logiczne utworzone na stosie, ale wartości logiczne są tworzone kilka razy na stosie, ponieważ funkcja jest rekurencyjna.

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;
}

To skanuje wzorem:

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

I tak dalej

A następnie zmiana wartości w tym wzorze po powrocie na każdej z funkcji skanowania. (Od dołu do góry):

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

I tak dalej

Ok jest to rozwiązanie, które

• używa tylko jednej dodatkowej długiej wartości do przechowywania pracy.
• nie używa rekurencji.
• jedno przejście tylko N, nawet N*N.
• będzie działać dla innych wartości n, ale będzie wymagał nowych definicji#.

#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;
    }

Właściwie. Jeśli po prostu chcesz uruchomić algorytm i wydrukować wyniki (tzn. nie przywracać ich, to można to łatwo zrobić w jednym przejściu. Problem pojawia się, gdy próbujesz zmodyfikować tablicę podczas uruchamiania algorytmu.

Oto moje rozwiązanie polega na dodaniu wartości wierszy/kolumn dla danego elementu (i,j) i wydrukowaniu go.

#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;
    }
}

Próbowałem rozwiązać ten problem w C#.

Użyłem dwóch zmiennych pętli (i I j) oprócz macierzy rzeczywistej i n reprezentującej jej Wymiar

Logika, którą próbowałem to:

1. Oblicz i dla wierszy i kolumn zaangażowanych w każdy koncentryczny kwadrat macierzy
2. przechowuj go w swoich narożnych komórkach (zapisałem je w kolejności zgodnej z ruchem wskazówek zegara)
3. dwie zmienne bool są używane do zachowania wartości dwóch narożników przy obliczaniu określonego kwadratu.
4. to proces zakończy się, gdy zewnętrzna pętla (i) jest w połowie drogi.
5. Oceń wyniki innych komórek na podstawie komórek narożnych (dla reszty i). Pomiń komórki narożne podczas tego procesu.
6. gdy osiągnę n, wszystkie komórki będą miały swój wynik z wyjątkiem komórek narożnych.
7. zaktualizuj komórki narożne. Jest to dodatkowa iteracja do długości n / 2 inna niż ograniczenie pojedynczego przejścia wymienione w problemie.

Kod:

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;
            }
        }
    }
}

Chociaż niemożliwe ze względu na ograniczenia, najbardziej efektywnym sposobem na to jest przemierzanie macierzy w nakładający się, naprzemienny sposób wiersza/kolumny, co uczyniłoby wzór podobny do układania cegieł w zygzakowaty sposób:

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

Używając tego, można przejść do każdego wiersza / kolumny, jak wskazano, a jeśli napotkasz 0 w dowolnym momencie, Ustaw zmienną logiczną i ponownie przejdź do tego wiersza / kolumny, ustawiając wpisy na 0, gdy idziesz.

Nie będzie to wymagało dodatkowej pamięci i będzie używaj tylko jednej zmiennej logicznej. Niestety, jeśli" daleko " krawędź jest ustawiona na all być 0, to jest najgorszy przypadek i przejść całą tablicę dwa razy.

Utwórz macierz wynikową i ustaw wszystkie wartości na 1. przejdź przez macierz danych, gdy tylko napotkasz 0, Ustaw kolumnę wiersza macierzy wyników na 0

Na końcu pierwszego przejścia macierz wyników będzie miała poprawną odpowiedź.

Wygląda dość prosto. Brakuje mi jakiejś sztuczki? Czy nie wolno Ci używać zestawu wyników?

EDIT:

Wygląda jak funkcja F#, ale to trochę oszustwo, ponieważ nawet jeśli robisz jedno przejście, funkcja może być rekurencyjny.

Wygląda na to, że ankieter próbuje dowiedzieć się, czy znasz Programowanie funkcyjne.

Cóż, wymyśliłem rozwiązanie jednokrotne, in-place (non-rekurencyjne), używając 4 boolów i 2 liczników pętli. Nie udało mi się zredukować go do 2 bools i 2 int, ale nie zdziwiłbym się, gdyby to było możliwe. Robi około 3 odczytów i 3 zapisów każdej komórki i powinno być O (N^2) czyli. liniowy w rozmiarze tablicy.

Zajęło mi kilka godzin, aby rozwiązać ten jeden-nie chciałbym musiał wymyślić go pod presją wywiadu! Jeśli zrobiłem booboo jestem zbyt zmęczony, by Zobacz też..

Um... Wybieram zdefiniowanie "single-pass" jako dokonywanie jednego zamiatania przez matrycę, zamiast dotykania każdej wartości raz! :-)

#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;
}

Mam nadzieję, że spodoba ci się Moje 1-pass C # solution

Możesz pobrać element za pomocą O(1) i potrzebujesz tylko przestrzeń jednego wiersza i jednej kolumny macierzy

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 pass, 2 booleans. Muszę tylko założyć, że indeksy liczb całkowitych w iteracjach się nie liczą.

To nie jest kompletne rozwiązanie, ale nie mogę przejść tego punktu.

Gdybym tylko mógł określić, czy 0 jest oryginalnym 0 LUB 1, które zostało przekonwertowane na 0, nie musiałbym używać -1 i to by działało.

Moje wyjście jest takie:

-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

Właśnie zdałem sobie sprawę, że można to zrobić tylko z 1 boolean pozostawiając 1 do ...?

Oto kod w 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

Nikt nie używa form binarnych? ponieważ jest tylko 1 i 0. Możemy użyć wektorów binarnych.

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

Oto test:

M = [ 0b10110,
      0b01110,
      0b11111,
      0b10111,
      0b11111 ]

print "Before..."
for i in M: print "{:0=5b}".format(i)

M = set1(M, len(M))
print "After..."
for i in M: print "{:0=5b}".format(i)

I wyjście:

Before...
10110
01110
11111
10111
11111
After...
00000
00000
00110
00000
00110

Możesz zrobić coś takiego, aby użyć jednego przejścia, ale matrycy wejścia i wyjścia:

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

Gdzie col(xy) to bity w kolumnie zawierającej punkt xy; row(xy) jest bitami w wierszu zawierającym punkt xy. {[5] } jest wielkością macierzy.

Następnie po prostu zapętlaj wejście. Być może rozszerzalne, aby być bardziej oszczędne miejsca?

Jeden skan macierzy, dwa booleany, bez rekurencji.

Jak uniknąć drugiego podania? Drugi przebieg jest potrzebny do wyczyszczenia wierszy lub kolumn, gdy zero pojawi się na ich końcu.

Jednak ten problem można rozwiązać, ponieważ kiedy skanujemy wiersz #i, znamy już status wiersza dla wiersza #i-1. Tak więc podczas skanowania rzędu #i możemy jednocześnie wyczyścić wiersz #i-1, jeśli jest to potrzebne.

To samo rozwiązanie działa dla kolumn, ale musimy skanować wiersze i kolumny jednocześnie, podczas gdy dane nie są zmieniane przez następną iterację.

Do przechowywania stanu pierwszego wiersza i pierwszej kolumny wymagane są dwie wartości logiczne, ponieważ ich wartości zostaną zmienione podczas wykonywania głównej części algorytmu.

Aby uniknąć dodawania kolejnych wartości logicznych, przechowujemy flagę "clear"dla wierszy i kolumn w pierwszym wierszu i kolumnie macierzy.

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();
}

Wygląda na to, że następujące prace bez dodatkowych wymagań przestrzennych:

Najpierw należy zauważyć, że mnożenie elementów wiersza razy elementów wiersza, w którym jest element, daje pożądaną wartość.

Aby nie używać żadnej dodatkowej przestrzeni (nie tworzyć nowej macierzy i jej wypełniać, ale zamiast tego stosować zmiany bezpośrednio do macierzy), zacznij od lewej górnej części macierzy i wykonaj obliczenia dla dowolnej macierzy ixi (która "zaczyna się" od (0,0)) przed rozważeniem dowolnego elementu z any index > i.

Hope this works (havent testet)

Jest to testowane dla różnych N W C++ i jest:
ONE PASS, dwa Boole, Brak rekurencji, brak dodatkowej pamięci, uchwyty dla dowolnie dużych N
(Jak dotąd żadne z rozwiązań tutaj nie spełnia tych wszystkich.)

Dokładniej, jestem zabawny dwa liczniki pętli są w porządku. Mam dwa const unsigned, które tylko istnieją, a nie są obliczane za każdym razem dla czytelności. Interwał pętli zewnętrznej wynosi [0, N], A interwał pętli wewnętrznej wynosi [1, n-1]. Instrukcja switch jest w pętli w większości istnieje, aby pokazać bardzo wyraźnie, że naprawdę jest to tylko jedno przejście.

Strategia Algorytmu:

Pierwszą sztuczką jest dla nas wiersz i kolumna z samej macierzy, aby zgromadzić zawartość macierzy, pamięć ta staje się dostępna przez odciążenie wszystkiego, co naprawdę musimy wiedzieć z pierwszego wiersza i kolumny na dwa booleany. Drugim trikiem jest uzyskanie dwóch przejść z jednego, wykorzystując symetrię pod-macierzy i jej indeksy.

Opis Algorytmu:

• skanuje pierwszy wiersz i przechowuje, jeśli wszystkie są w układzie logicznym, zrób to samo dla pierwszej kolumny przechowującej wynik w drugim układzie logicznym.
• Dla pod-macierzy z wyłączeniem pierwszego wiersza i pierwszej kolumny: iteracja przez, Od lewej do prawej, od góry do dołu, jak można by przeczytać akapit. Po odwiedzeniu każdego elementu, Odwiedź również odpowiedni element, który zostanie odwiedzony, jeśli odwiedzisz sub-matrycę w odwrotnej kolejności. Na każdy odwiedzony element i jego wartość do miejsca, w którym jego wiersz przecina pierwszą kolumnę, a także i jego wartość do miejsca, w którym jego kolumna przecina pierwszy wiersz.
• Po osiągnięciu środka sub-matrycy, Kontynuuj odwiedzanie dwóch elementów jednocześnie, jak powyżej. Jednak Teraz ustaw wartość odwiedzanych elementów na i gdzie jego wiersz przecina pierwszą kolumnę oraz gdzie jego kolumna przecina pierwszy wiersz. Po tym, sub-matryca jest kompletna.
• użyj dwóch zmiennych logicznych obliczane na początku, aby ustawić pierwszy wiersz i pierwszą kolumnę na ich prawidłowe wartości.

Implementacja Szablonów 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, zdaję sobie sprawę, że to nie jest całkiem dopasowanie, ale mam go w jednym przejściu za pomocą bool i Bajt zamiast dwóch bool... blisko. Nie ręczyłbym też za jego skuteczność, ale tego typu pytania często wymagają mniej niż optymalnych rozwiązań.

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; }
        }
    }
}

Możesz to zrobić w pewnym sensie w jednym przejściu -- jeśli nie liczysz dostępu do matrycy w kolejności dostępu losowego, co eliminuje korzyści płynące z robienia tego jednoprzebiegowego w pierwszej kolejności (pamięć podręczna-spójność/pamięć-przepustowość).

[edit: proste, ale złe rozwiązanie usunięte]

Powinieneś uzyskać lepszą wydajność niż jakakolwiek metoda jednoprzebiegowa, wykonując ją w dwóch przebiegach: jeden do gromadzenia informacji o wierszach/kolumnach, a drugi do zastosowania. Dostęp do tablicy (w kolejności rzędu-major) jest spójny; dla tablic przekroczenie rozmiaru bufora (ale którego wiersze mogą zmieścić się w buforze), dane powinny być odczytywane z pamięci dwa razy i przechowywane raz:

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;
        }
    }
}

Najprostsze rozwiązanie, jakie przychodzi mi do głowy, jest wklejone poniżej. Logika polega na zapisaniu, który wiersz i kolumnę ustawić zero podczas iteracji.

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);
    }
}

Oto moja implementacja Ruby z dołączonym testem, zajmie to o (MN) przestrzeń. Jeśli chcemy mieć aktualizację w czasie rzeczywistym (jak pokazywać wyniki gdy znajdziemy zera, zamiast czekać na pierwszą pętlę znajdowania zer) możemy po prostu utworzyć kolejną zmienną klasy, taką jak @output i kiedy znajdziemy zero, aktualizujemy @output, a nie @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

Poniższy kod tworzy macierz o rozmiarach m,n. najpierw decyduje o wymiarach macierzy. Chciałem wypełnić matrycę[m] [n] losowo o numerach od 0..10. Następnie utwórz inną macierz o tych samych wymiarach i wypełnij ją-1s (macierz końcowa). Następnie przejdź przez początkową matrycę, aby zobaczyć, czy trafisz 0. Po naciśnięciu na miejscu (x, y), przejdź do ostatecznej matrycy i wypełnij wiersz x z 0s i Kolumna y z 0s. Na końcu odczytać przez macierz końcową, jeśli wartość wynosi -1 (oryginał wartość) skopiuj wartość w tym samym miejscu macierzy początkowej do finalnej.

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;
}

Oto moje rozwiązanie. Jak widać z kodu, biorąc pod uwagę macierz M * N, ustawia cały wiersz na zero, gdy tylko wykryje zero w tym wierszu.złożoność czasowa mojego rozwiązania to O ( M * N). Udostępniam całą klasę, która ma statycznie wypełnioną tablicę do testowania i metodę display array, aby zobaczyć wynik w konsoli.

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 - przejechałem wejście tylko raz, ale użyłem nowej tablicy i tylko dwóch dodatkowych zmiennych logicznych.

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();

    }