Algorithmus zum Nullsetzen aller "schlechten" Spalten und Zeilen

Question

Gegebene Byte-Matrix (alle Werte sind 1 Bit im Speicher), rufen Sie es roh oder Spalte "schlecht", wenn es mindestens eine Null hat. Finde einen Algorithmus, der O (1) zusätzlichen Speicher benötigt.

Ich weiß nicht, wie es geht, ohne einen anderen Wert wie -1 oder eine andere doppelte Matrix zu haben, um bereits gefundene Nullen zu verfolgen und sie nicht mit Nullen zu verwechseln, die wir gefüllt haben.

Answer 1

Angenommen, A ist die Byte-Matrix, die Ihnen zur Verfügung gestellt wird. Diese Lösung verwendet konstanten zusätzlichen Speicherplatz. Verwenden Sie die erste Zeile und Spalte in der Matrix, um als Markierung zu fungieren. Nur ein zusätzliches Flag (hier r1) für row1 ist erforderlich.

void setZeroes(vector<vector<int> > &A) { 
    int m = A.size(); 
    int n = A[0].size(); 
    int r1 = 1; //row1 
    for(int j = 0; j < n; j++){ 
     r1 *= A[0][j]; 
    } 
    for(int i = 1; i < m; i++){ //first row skipped 
     for(int j = 0; j < n; j++){ 
      A[0][j] *= A[i][j]; //Marking Colm 
      A[i][0] *= A[i][j]; //Marking rows, skipping row#1 
     } 
    } 
    for(int i = 1; i < m; i++){ 
     for(int j = 1; j < n; j++){ 
      A[i][j] = A[0][j] * A[i][0]; 
     } 
    } 
    //At last, update colm1. 
    for(int j = 1; j < m; j++){ 
     A[j][0] *= A[0][0]; 
    } 
    //At last, update row1. 
    for(int j = 0; j < n; j++){ 
     A[0][j] *= r1; 
    } 
} 

Answer 2

Dieser Algorithmus verwendet O (1) -Raum. Hier sind die Schritte:

1. Finden Sie eine erste Zeile mit allen 1 Werten. Wenn es keine solche Zeile gibt, enthalten alle Zeilen mindestens eine 0, also sollte jede Matrix eine 0 sein. Behalten Sie den Index der Zeile in Variable I.

2. Verwenden Sie I-ten Zeile als Flag, um Wert für jede Spalte, d. H. & ganze Spalte und Speichern in I-ten Zeile.

3. & jede Zeile außer I-te und Wert auf die Elemente dieser bestimmten Zeile setzen, dh 1 Zeile nehmen wenn mindestens eine 0 ganze Reihe auf 0 gesetzt ist sonst Zeile mit allen 1en verlassen, zweite Reihe nehmen usw. außer ich die Reihe.
4. & I-te Zeile zu allen anderen Zeilen, d. H. A[i][j] &= A[I][j] für alle i <> I und j=0,1,...,A[I].length-1.

Das ist alles !!!

Als Beispiel haben wir

1 1 1 0 1 0
1 1 1 1 1 1
1 0 1 1 1 1
1 1 1 1 1 1
0 1 1 1 1 0

Nach ersten Schritt werden wir I = 1 die zweite Reihe finden.

Dann nur 2. Reihe ändern wir die Matrix nach dem zweiten Schritt wurde (es geändert 1., 2., 4. und letzten Elemente auf 0, weil dadurch, dass Spalten 0s gefunden):

1 1 1 0 1 0
0 0 1 0 1 0
1 0 1 1 1 1
1 1 1 1 1 1
0 1 1 1 1 0

nach Schritt 3 Matrix wurde (wir werden 0s zu den Reihen gesetzt, die mindestens eine 0 excep 2. Reihe hat):

0 0 0 0 0 0
0 0 1 0 1 0
0 0 0 0 0 0
1 1 1 1 1 1
0 0 0 0 0 0

Nach Schritt 4 Matrix wurde folgende (wir & Operationen durch alle Spalten tun):

0 0 0 0 0 0
0 0 1 0 1 0
0 0 0 0 0 0
0 0 1 0 1 0
0 0 0 0 0 0

Das ist die Matrix die wir suchen.