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

Biorąc pod uwagę macierz NxN z 0 i 1. Ustaw każdy wiersz zawierający a 0na wszystkie 0s i ustaw każdą kolumnę zawierającą a 0na wszystkie 0s.

Na przykład

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

prowadzi do

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

Inżynier Microsoft powiedział mi, że istnieje rozwiązanie, które nie wymaga dodatkowej pamięci, tylko dwie zmienne boolowskie i jeden przebieg, więc szukam odpowiedzi.

Przy okazji, wyobraź sobie, że jest to macierz bitowa, dlatego tylko 1s i 0s mogą być w macierzy.

Ok, więc jestem zmęczony, bo tu jest 3 rano, ale mam pierwszą próbę w miejscu z dokładnie 2 przebiegami na każdej liczbie w macierzy, więc w O (NxN) i jest liniowa w rozmiarze matrycy.

Używam pierwszej kolumny i pierwszego wiersza jako znaczników, aby wiedzieć, gdzie są wiersze / kolumny zawierające tylko jedynki. Następnie są 2 zmienne l i c do zapamiętania, jeśli pierwszy wiersz / kolumna to również 1. Tak więc pierwsze przejście ustawia znaczniki, a resztę resetuje do zera.

Drugi przebieg ustawia 1 w miejscach, w których rzędy i kolumny były oznaczone jako 1, i resetuje 1 linię / kolumnę w zależności od l i c.

Wątpię mocno, że da się zrobić w 1 przejściu, ponieważ kwadraty na początku zależą od kwadratów na końcu. Może moje drugie przejście będzie bardziej wydajne ...

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)

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

Aktualizacja

Wydaje się, że ludzie myślą, że ograniczając N do jakiejś stałej wartości (powiedzmy 8), można rozwiązać ten problem w jednym przebiegu. Cóż, to a) pomijam sedno ib) nie jest to oryginalne pytanie. Nie zadałbym pytania na temat sortowania i oczekiwałbym odpowiedzi zaczynającej się od „zakładając, że chcesz posortować tylko 8 rzeczy ...”.

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

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

Za pomocą zygzaka przeskanuj całą macierz Z WYJĄTKIEM ostatniego wiersza / kolumny. W każdym elemencie ustawiasz wartość w ostatnim wierszu / kolumnie jako logiczne AND samego siebie z wartością w bieżącym elemencie. Innymi słowy, jeśli trafisz 0, ostatni wiersz / kolumna zostanie ustawiony na 0. Jeśli wybierzesz 1, wartość w ostatnim wierszu / kolumnie będzie wynosić 1 tylko wtedy, gdy już wynosiła 1. W każdym razie ustaw bieżący element na 0.

Kiedy skończysz, ostatni wiersz / kolumna powinien mieć 1s, jeśli odpowiadająca mu kolumna / wiersz został wypełniony 1s.

Wykonaj liniowe skanowanie ostatniego wiersza i kolumny i wyszukuj jedynki. Ustaw 1 w odpowiednich elementach w treści macierzy, gdzie ostatni wiersz i kolumna to jedynki.

Kodowanie będzie trudne, aby uniknąć błędów typu off-by-one itp., Ale powinno działać w jednym przebiegu.

Mam tutaj rozwiązanie, które działa w jednym przebiegu i wykonuje całe przetwarzanie „na miejscu” bez dodatkowej pamięci (z wyjątkiem powiększania stosu).

Używa rekurencji, aby opóźnić pisanie zer, co oczywiście zniszczyłoby macierz dla innych wierszy i kolumn:

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

Myślę, że to nie jest wykonalne. Kiedy jesteś na pierwszym kwadracie, a jego wartość wynosi 1, nie masz możliwości sprawdzenia, jakie są wartości innych kwadratów w tym samym wierszu i kolumnie. Musisz więc je sprawdzić i jeśli jest zero, wróć do pierwszego kwadratu i zmień jego wartość na zero. Polecam zrobić to w dwóch przebiegach - pierwszy przebieg zbiera informacje o tym, które wiersze i kolumny należy wyzerować (informacje są przechowywane w tablicy, więc używamy dodatkowej pamięci). Drugi przebieg zmienia wartości. Wiem, że nie jest to rozwiązanie, którego szukasz, ale myślę, że jest praktyczne. Ograniczenia podane przez Ciebie sprawiają, że problem jest nierozwiązywalny.

Mogę to zrobić z dwiema zmiennymi całkowitymi i dwoma przebiegami (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ć za jednym razem

zapis 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 wypisz wszystkie wartości jako 0 dla wartości i i j zapisanych w aib pozostałe wartości to 1 tj. (3,3) (3,4) (5,3) i (5,4)

Innym rozwiązaniem, które wymaga dwóch przebiegów, jest gromadzenie AND w poziomie i w pionie:

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    

Pomyślałem, że mógłbym zaprojektować taki algorytm przy użyciu bitów parzystości , kodów Hamminga lub programowania dynamicznego , prawdopodobnie używając tych dwóch wartości logicznych jako liczby 2-bitowej, ale nie odniosłem jeszcze sukcesu.

Czy możesz ponownie sprawdzić opis problemu ze swoim inżynierem i powiadomić nas o tym? Jeśli tam jest rzeczywiście rozwiązaniem, chcę zachować Zmniejszanie problemu.

Zachowaj jedną zmienną, aby śledzić, jakie są wszystkie wiersze połączone operatorem AND.

Jeśli wiersz ma wartość -1 (wszystkie jedynki), ustaw następny wiersz jako odniesienie do tej zmiennej

Jeśli wiersz jest czymś innym niż 0. Możesz zrobić wszystko za jednym razem. Kod pseudo:

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 przebiegu - ale jest tu założenie, że N jest wystarczająco małe, aby procesor mógł wykonać operacje arytmetyczne w jednym wierszu, w przeciwnym razie będziesz musiał zapętlić każdy wiersz, aby określić, czy to wszystko 1 s lub nie, jak sądzę. Ale biorąc pod uwagę, że pytasz o algorytmy i nie ograniczasz mojego sprzętu, mógłbym po prostu rozpocząć swoją odpowiedź od „Zbuduj procesor obsługujący 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, a zmienne iloczynu AND służą do implementacji problemu. (Mogłem zapętlić arr z arytmetyką wskaźników, aby sprawdzić poprawność mojej pracy, ale raz 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;
}

Daje to 0, 0, 6, 0, 6, co jest wynikiem dla podanych danych wejściowych.

Lub w PHP, jeśli ludzie uważają, że moje gry na stackach w C oszukują (sugeruję, że tak nie jest, ponieważ powinienem móc przechowywać macierz 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);

Czy coś mi brakuje?

Niezłe wyzwanie. To rozwiązanie używa tylko dwóch wartości logicznych utworzonych 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 w następujący sposób:

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 dla 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

Okej, to jest rozwiązanie

• wykorzystuje tylko jedną bardzo długą wartość do przechowywania roboczego.
• nie używa rekursji.
• jeden przebieg tylko N, nawet nie N * N.
• będzie działać dla innych wartości N, ale będzie potrzebować nowych #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;
    }

Tak właściwie. Jeśli chcesz tylko uruchomić algorytm i wydrukować wyniki (tj. Nie je przywrócić, możesz to łatwo zrobić w jednym przebiegu) .Kłopot pojawia się, gdy próbujesz zmodyfikować tablicę w trakcie wykonywania algorytmu.

Oto moje rozwiązanie. Po prostu polega na połączeniu wartości wierszy / kolumn dla elementu Givein (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 rzeczywistej macierzy in reprezentującej jej wymiar

Logika, której próbowałem:

1. Oblicz AND dla wierszy i cols zaangażowanych w każdy koncentryczny kwadrat macierzy
2. Przechowuj go w komórkach narożnych (zapisałem je w kolejności przeciwnej do ruchu wskazówek zegara)
3. Dwie zmienne bool są używane do zachowania wartości dwóch rogów podczas obliczania konkretnego kwadratu.
4. Ten proces zakończy się, gdy zewnętrzna pętla (i) znajdzie się w połowie drogi.
5. Oceń wyniki innych komórek na podstawie komórek narożnych (do końca i). Pomiń komórki narożne podczas tego procesu.
6. Kiedy osiągnę n, wszystkie komórki miałyby 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, o którym mowa w zadaniu.

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

One Pass - przeszedłem dane wejściowe tylko raz, ale użyłem nowej tablicy i tylko dwóch dodatkowych zmiennych boolowskich.

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

    }

Chociaż jest to niemożliwe, biorąc pod uwagę ograniczenia, najbardziej efektywnym przestrzennie sposobem na to jest przechodzenie przez matrycę w sposób nakładający się, naprzemienny rząd / kolumna, co dałoby wzór podobny do układania cegieł w zygzak:

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

Używając tego, przejdziesz do każdego wiersza / kolumny, jak wskazano, i jeśli napotkasz 0 w dowolnym momencie, ustaw zmienną logiczną i ponownie przejrzyj ten wiersz / kolumnę, ustawiając wpisy na 0.

Nie będzie to wymagało dodatkowej pamięci i użyje tylko jednej zmiennej boolowskiej. Niestety, jeśli „daleka” krawędź jest ustawiona na 0, jest to najgorszy przypadek i przechodzisz przez całą tablicę dwa razy.

utwórz macierz wyników i ustaw wszystkie wartości na 1. przejdź przez macierz danych, gdy tylko zostanie napotkane 0, ustaw kolumnę wiersza macierzy wyników na 0

Pod koniec pierwszego przejścia macierz wyników będzie zawierała poprawną odpowiedź.

Wygląda całkiem prosto. Czy brakuje mi jakiejś sztuczki? Czy nie możesz używać zestawu wyników?

EDYTOWAĆ:

Wygląda jak funkcja F #, ale to trochę oszukuje, ponieważ nawet jeśli wykonujesz pojedynczy przebieg, funkcja może być rekurencyjna.

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

Cóż, wymyśliłem jednoprzebiegowe, na miejscu (nierekurencyjne) rozwiązanie wykorzystujące 4 boole i 2 liczniki pętli. Nie udało mi się zredukować go do 2 booli i 2 int, ale nie zdziwiłbym się, gdyby to było możliwe. Wykonuje około 3 odczytów i 3 zapisów dla każdej komórki i powinno być O (N ^ 2) tj. liniowy w rozmiarze tablicy.

Rozwikłanie tego rozwiązania zajęło mi kilka godzin - nie chciałbym wymyślać tego pod presją wywiadu! Jeśli zrobiłem booboo, jestem zbyt zmęczony, żeby to zauważyć ...

Um ... Zdecydowałem się zdefiniować „jednoprzebiegowe” jako wykonanie jednego przeciągnięcia po macierzy, 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 jednoprzebiegowe rozwiązanie C #

możesz pobrać element za pomocą O (1) i potrzebujesz tylko miejsca na jeden wiersz i jedną kolumnę 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 przebieg, 2 wartości logiczne. Muszę tylko założyć, że indeksy całkowite 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, czy 1, które zostało przekonwertowane na 0, nie musiałbym używać -1 i to zadziałałoby.

Moje wyniki wyglądają następująco:

-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

Oryginalność mojego podejścia polega na wykorzystaniu pierwszej połowy badania wiersza lub kolumny do określenia, czy zawiera 0, a ostatniej połowy do ustawienia wartości - odbywa się to poprzez spojrzenie na x i szerokość-x, a następnie y i wysokość -y w każdej iteracji. Opierając się na wynikach pierwszej połowy iteracji, jeśli znaleziono 0 w wierszu lub kolumnie, używam ostatniej połowy iteracji, aby zmienić 1 na -1.

Właśnie zdałem sobie sprawę, że można to zrobić mając tylko 1 wartość logiczną, która pozostawia 1 do ...?

Publikuję to, mając nadzieję, że ktoś powie: „Ach, po prostu zrób to ...” (I spędziłem zbyt dużo czasu, żeby nie publikować).

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 formularzy binarnych? ponieważ jest to tylko 1 i 0. Możemy używać 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)

A wynik:

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

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

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

gdzie col(xy)jest bitami w kolumnie zawierającej punkt xy; row(xy)to bity w wierszu zawierającym punkt xy. njest rozmiarem macierzy.

Następnie po prostu wykonaj pętlę nad wejściem. Czy istnieje możliwość rozbudowy, aby zajmować więcej miejsca?

Jeden skan macierzy, dwie wartości logiczne, bez rekursji.

Jak uniknąć drugiego przejścia? Drugie przejście jest potrzebne do wyczyszczenia wierszy lub kolumn, gdy na ich końcu pojawi się zero.

Jednak ten problem można rozwiązać, ponieważ kiedy skanujemy wiersz #i, znamy już stan wiersza dla wiersza # i-1. Tak więc, podczas skanowania wiersza #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 kolejną 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 większej liczby wartości logicznych, przechowujemy flagę „wyczyść” 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 nie wymagają dodatkowego miejsca:

Najpierw zauważ, że pomnożenie elementów wiersza razy elementów wiersza, w którym znajduje się element, daje żądaną wartość.

Aby nie używać dodatkowej przestrzeni (nie tworzyć nowej macierzy i wypełniać ją, ale zamiast tego bezpośrednio wprowadzać zmiany w macierzy), należy rozpocząć od lewej górnej części macierzy i wykonać obliczenia dla dowolnej macierzy ixi (która „zaczyna się” od (0 , 0)) przed rozważeniem dowolnego elementu o dowolnym indeksie> i.

mam nadzieję, że to zadziała (nie mam testu)

Jest to TESTOWANE dla różnych N w C ++ i jest:
JEDNO PRZEJŚCIE , DWA BOOLE , BEZ REKURSJI , BEZ DODATKOWEJ PAMIĘCI , PRZYSŁUGUJE SIĘ NA DROBNO DUŻE N
(Póki co żadne z przedstawionych tutaj rozwiązań nie obsługuje WSZYSTKICH).

Mówiąc dokładniej, zabawne są dwa liczniki pętli. Mam dwie const unsigneds, które istnieją tylko zamiast być obliczane za każdym razem dla czytelności. Interwał pętli zewnętrznej to [0, N], a przedział pętli wewnętrznej to [1, n - 1]. Instrukcja switch jest w pętli głównie po to, aby bardzo wyraźnie pokazać, że tak naprawdę jest to tylko jeden przebieg.

Strategia algorytmu:

Pierwszą sztuczką jest dla nas wiersz i kolumna z samej macierzy, aby zgromadzić zawartość macierzy, ta pamięć staje się dostępna poprzez przeniesienie wszystkiego, co naprawdę musimy wiedzieć, z pierwszego wiersza i kolumny na dwie wartości logiczne. Druga sztuczka polega na uzyskaniu dwóch przebiegów z jednego, używając symetrii podmacierzy i jej indeksów.

Streszczenie algorytmu:

• Przeskanuj pierwszy wiersz i zapisz, jeśli wszystkie są wartościami logicznymi, zrób to samo dla pierwszej kolumny, przechowując wynik w drugiej wartości logicznej.
• W przypadku macierzy podrzędnej z wyłączeniem pierwszego wiersza i pierwszej kolumny: iteruj od lewej do prawej, od góry do dołu, tak jak czyta się akapit. Odwiedzając każdy element, odwiedź również odpowiedni element, który zostałby odwiedzony, gdyby odwiedzono podmacierz w odwrotnej kolejności. Dla każdego odwiedzanego elementu ORAZ jego wartości do miejsca, w którym jego wiersz przecina pierwszą kolumnę, a także ORAZ jego wartości do miejsca, w którym jego kolumna przecina pierwszy wiersz.
• Po osiągnięciu środka podmacierzy kontynuuj odwiedzanie dwóch elementów jednocześnie, jak powyżej. Jednak teraz ustaw wartość odwiedzanych elementów na AND, gdzie jego wiersz przecina pierwszą kolumnę i gdzie jego kolumna przecina pierwszy wiersz. Następnie podmacierz jest kompletna.
• Użyj dwóch zmiennych logicznych obliczonych na początku, aby ustawić pierwszy wiersz i pierwszą kolumnę na ich prawidłowe wartości.

Implementacja w języku C ++ oparta na szablonach:

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 do końca pasuje, ale otrzymałem to w jednym przebiegu, używając bool i bajtu zamiast dwóch bool ... blisko. Nie ręczyłbym również 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 jednym przebiegu - jeśli nie liczysz dostępu do matrycy w kolejności losowej, co eliminuje korzyści płynące z robienia tego w jednym przejściu (spójność pamięci podręcznej / przepustowość pamięci).

[edytuj: usunięto proste, ale złe rozwiązanie]

Powinieneś uzyskać lepszą wydajność niż jakakolwiek metoda jednoprzebiegowa, wykonując to w dwóch przebiegach: jeden do gromadzenia informacji o wierszach / kolumnach, a drugi do ich zastosowania. Dostęp do tablicy (w kolejności wiersz-główny) jest spójny; dla tablic przekraczających rozmiar pamięci podręcznej (ale których wiersze mieszczą się w pamięci podręcznej), dane powinny być odczytywane z pamięci dwukrotnie i zapisywane 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 kolumna mają 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, zajęłoby to miejsce O (MN). Jeśli chcemy aktualizacji w czasie rzeczywistym (np. Aby pokazać wyniki, gdy znajdziemy zera, zamiast czekać na pierwszą pętlę znajdowania zer), możemy po prostu utworzyć inną zmienną klasy, jak @outputi zawsze, gdy znajdziemy zero, aktualizujemy, @outputa 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 rozmiarze m, n. Najpierw zdecyduj o wymiarach macierzy. Chciałem wypełnić macierz [m] [n] losowo liczbami z zakresu 0..10. Następnie utwórz kolejną macierz o tych samych wymiarach i wypełnij ją -1s (ostateczna macierz). Następnie wykonaj iterację przez początkową macierz, aby zobaczyć, czy trafisz 0. Kiedy trafisz w położenie (x, y), przejdź do ostatniej macierzy i wypełnij wiersz x zerami, a kolumnę y zerami. Na koniec przeczytaj końcową macierz, jeśli wartość wynosi -1 (wartość oryginalna), skopiuj wartość w tym samym miejscu początkowej macierzy do ostatecznej.

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 ona cały wiersz na zero po sprawdzeniu zera w tym wierszu. Złożoność czasowa mojego rozwiązania wynosi O (M * N). Udostępniam całą klasę, która ma statyczną wypełnioną tablicę do testowania i metodę tablicy wyświetlania, 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("");
    }

}

}