Gegeben eine NxN-Matrix mit 0s und 1s. Setzen Sie jede Zeile, die a 0
auf alle 0
s enthält , und jede Spalte, die a 0
auf alle 0
s enthält.
Beispielsweise
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
führt zu
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
Ein Microsoft-Ingenieur sagte mir, dass es eine Lösung gibt, die keinen zusätzlichen Speicher, nur zwei boolesche Variablen und einen Durchgang umfasst. Deshalb suche ich nach dieser Antwort.
Übrigens, stellen Sie sich vor, es ist eine Bitmatrix, daher dürfen nur 1s und 0s in der Matrix sein.
algorithm
optimization
puzzle
Jaircazarin-altes Konto
quelle
quelle
Antworten:
Ok, ich bin müde, da es hier 3 Uhr morgens ist, aber ich habe einen ersten Versuch mit genau 2 Durchgängen für jede Zahl in der Matrix, also in O (NxN) und es ist linear in der Größe der Matrix.
Ich benutze die erste Spalte und die erste Zeile als Markierungen, um zu wissen, wo Zeilen / Spalten mit nur Einsen sind. Dann gibt es 2 Variablen l und c, an die man sich erinnern muss, wenn die erste Zeile / Spalte auch alle Einsen sind. Der erste Durchgang setzt also die Markierungen und setzt den Rest auf Null zurück.
Der zweite Durchgang setzt 1 an Stellen, an denen Zeilen und Spalten als 1 markiert wurden, und setzt die erste Zeile / Spalte in Abhängigkeit von l und c zurück.
Ich bezweifle stark, dass ich in einem Durchgang fertig sein kann, da Quadrate am Anfang von Quadraten am Ende abhängen. Vielleicht kann mein 2. Durchgang effizienter gemacht werden ...
quelle
Dies kann nicht in einem Durchgang erfolgen, da sich ein einzelnes Bit in beliebiger Reihenfolge auf die Bits davor und danach auswirkt. IOW Unabhängig von der Reihenfolge, in der Sie das Array durchlaufen, können Sie später auf eine 0 stoßen, was bedeutet, dass Sie zurückgehen und eine vorherige 1 in eine 0 ändern müssen.
Aktualisieren
Die Leute scheinen zu glauben, dass man dies durch einen einzigen Durchgang lösen kann, indem man N auf einen festen Wert (z. B. 8) beschränkt. Nun, das ist a) der Punkt fehlt und b) nicht die ursprüngliche Frage. Ich würde keine Frage zum Sortieren posten und eine Antwort erwarten, die anfing "vorausgesetzt, Sie möchten nur 8 Dinge sortieren ...".
Das heißt, es ist ein vernünftiger Ansatz, wenn Sie wissen, dass N tatsächlich auf 8 beschränkt ist. Meine Antwort oben beantwortet die ursprüngliche Frage, die keine solche Einschränkung aufweist.
quelle
Meine Idee ist es also, die Werte in der letzten Zeile / Spalte als Flag zu verwenden, um anzuzeigen, ob alle Werte in der entsprechenden Spalte / Zeile 1s sind.
Verwenden eines Zick-Zack-Scans durch die gesamte Matrix mit Ausnahme der letzten Zeile / Spalte. Bei jedem Element setzen Sie den Wert in der letzten Zeile / Spalte auf das logische UND von sich selbst mit dem Wert im aktuellen Element. Mit anderen Worten, wenn Sie eine 0 drücken, wird die letzte Zeile / Spalte auf 0 gesetzt. Wenn Sie eine 1 wählen, ist der Wert in der letzten Zeile / Spalte nur dann 1, wenn er bereits 1 war. Setzen Sie in jedem Fall das aktuelle Element auf 0.
Wenn Sie fertig sind, sollte Ihre letzte Zeile / Spalte 1s haben, wenn die entsprechende Spalte / Zeile mit 1s gefüllt wurde.
Führen Sie einen linearen Scan durch die letzte Zeile und Spalte durch und suchen Sie nach 1s. Setzen Sie 1s in die entsprechenden Elemente im Hauptteil der Matrix, wobei die letzte Zeile und Spalte beide 1s sind.
Das Codieren ist schwierig, um Fehler usw. zu vermeiden, aber es sollte in einem Durchgang funktionieren.
quelle
Ich habe hier eine Lösung, die in einem einzigen Durchgang ausgeführt wird und die gesamte Verarbeitung "an Ort und Stelle" ohne zusätzlichen Speicher ausführt (außer zum Erweitern des Stapels).
Es verwendet Rekursion, um das Schreiben von Nullen zu verzögern, was natürlich die Matrix für die anderen Zeilen und Spalten zerstören würde:
quelle
Ich denke nicht, dass es machbar ist. Wenn Sie sich auf dem ersten Quadrat befinden und dessen Wert 1 ist, können Sie die Werte der anderen Quadrate in derselben Zeile und Spalte nicht ermitteln. Sie müssen diese also überprüfen. Wenn es eine Null gibt, kehren Sie zum ersten Quadrat zurück und ändern Sie den Wert in Null. Ich empfehle, dies in zwei Durchgängen zu tun - im ersten Durchgang werden Informationen darüber gesammelt, welche Zeilen und Spalten auf Null gesetzt werden müssen (die Informationen werden in einem Array gespeichert, sodass wir zusätzlichen Speicher verwenden). Der zweite Durchgang ändert die Werte. Ich weiß, dass dies nicht die Lösung ist, nach der Sie suchen, aber ich denke, es ist eine praktische. Die von Ihnen angegebenen Einschränkungen machen das Problem unlösbar.
quelle
Ich kann es mit zwei ganzzahligen Variablen und zwei Durchgängen machen (bis zu 32 Zeilen und Spalten ...)
quelle
~
invertiert alle Bits in einer Variablen. Aus 0x00000000 wird 0x00000000. Ich beginne im Grunde mit allen und lösche das Bit für eine Zeile / Spalte, wenn ich eine 0 finde. CompleteCols hat die Bits 2 und 3 gesetzt und CompleteRows hat die Bits 2 und 4 gesetzt (0 basierend).Das Problem kann in einem Durchgang gelöst werden
Speichern der Matrix in einem i X j -Array.
Jetzt drucken Sie alle Werte als 0 für die in a und b gespeicherten Werte von i und j. Die restlichen Werte sind 1, dh (3,3) (3,4) (5,3) und (5,4).
quelle
Eine andere Lösung, die zwei Durchgänge benötigt, besteht darin, UNDs horizontal und vertikal zu akkumulieren:
Ich dachte, ich könnte einen solchen Algorithmus unter Verwendung von Paritätsbits , Hamming-Codes oder dynamischer Programmierung entwerfen, möglicherweise unter Verwendung dieser beiden Booleschen Werte als 2-Bit-Zahl, aber ich hatte noch keinen Erfolg.
Können Sie bitte die Problemstellung mit Ihrem Techniker überprüfen und uns Bescheid geben? Wenn es ist in der Tat eine Lösung, möchte ich auf das Problem halten kratzen.
quelle
Behalten Sie eine einzelne Variable bei, um zu verfolgen, was alle Zeilen UND-verknüpft sind.
Wenn eine Zeile -1 (alle 1s) ist, machen Sie die nächste Zeile zu einem Verweis auf diese Variable
Wenn eine Zeile alles andere als eine 0 ist, können Sie alles in einem Durchgang ausführen. Pseudocode:
Das sollte es in einem einzigen Durchgang tun - aber hier wird davon ausgegangen, dass N klein genug ist, damit die CPU in einer einzelnen Zeile rechnen kann. Andernfalls müssen Sie jede Zeile durchlaufen, um festzustellen, ob alles vorhanden ist 1s oder nicht, glaube ich. Aber wenn Sie nach Algen fragen und meine Hardware nicht einschränken, würde ich meine Antwort einfach mit "Erstellen Sie eine CPU, die N-Bit-Arithmetik unterstützt ..." beginnen.
Hier ist ein Beispiel, wie es in C gemacht werden kann. Hinweis Ich argumentiere, dass Werte und arr zusammen das Array darstellen und p und numproduct meine Iterator- und AND-Produktvariablen sind, die zur Implementierung des Problems verwendet werden. (Ich hätte arr mit Zeigerarithmetik durchlaufen können, um meine Arbeit zu validieren, aber einmal war genug!)
Dies erzeugt 0, 0, 6, 0, 6, was das Ergebnis für die gegebenen Eingaben ist.
Oder in PHP, wenn die Leute denken, dass meine Stack-Spiele in C betrügen (ich schlage Ihnen vor, dass dies nicht der Fall ist, weil ich die Matrix nach Belieben speichern kann):
Vermisse ich etwas
quelle
Schöne Herausforderung. Diese Lösung verwendet nur zwei Boolesche Werte, die auf dem Stapel erstellt wurden. Die Booleschen Werte werden jedoch mehrmals auf dem Stapel erstellt, da die Funktion rekursiv ist.
Dies scannt in einem Muster wie:
und so weiter
Ändern Sie dann die Werte in diesem Muster bei der Rückkehr für jede der Scanfunktionen. (Prost):
und so weiter
quelle
Okay, das ist eine Lösung, die
quelle
Tatsächlich. Wenn Sie nur den Algorithmus ausführen und die Ergebnisse ausdrucken möchten (dh nicht wiederherstellen möchten, können Sie dies problemlos in einem Durchgang tun. Das Problem tritt auf, wenn Sie versuchen, das Array während der Ausführung des Algorithmus zu ändern.
Hier ist meine Lösung. Es geht lediglich darum, die Zeilen- / Spaltenwerte für das Element eines Giveins (i, j) UND-verknüpft und auszudrucken.
quelle
Ich habe versucht, dieses Problem in C # zu lösen.
Ich habe zwei Schleifenvariablen (i und j) verwendet, abgesehen von der tatsächlichen Matrix und n, die ihre Dimension darstellen
Die Logik, die ich versucht habe, ist:
Code:
quelle
Ein Durchgang - Ich habe die Eingabe nur einmal durchlaufen, aber ein neues Array und nur zwei zusätzliche boolesche Variablen verwendet.
quelle
Angesichts der Einschränkungen ist dies zwar unmöglich, aber die platzsparendste Methode besteht darin, die Matrix in einer überlappenden, abwechselnden Zeilen- / Spaltenform zu durchlaufen, wodurch ein Muster entsteht, das dem Verlegen von Ziegeln im Zick-Zack ähnelt:
Wenn Sie dies verwenden, gehen Sie wie angegeben in jede Zeile / Spalte. Wenn Sie zu irgendeinem Zeitpunkt auf eine 0 stoßen, legen Sie eine boolesche Variable fest und gehen Sie diese Zeile / Spalte erneut durch, wobei Sie die Einträge auf 0 setzen.
Dies erfordert keinen zusätzlichen Speicher und verwendet nur eine boolesche Variable. Wenn die "ferne" Kante auf 0 gesetzt ist, ist dies leider der schlimmste Fall, und Sie durchlaufen das gesamte Array zweimal.
quelle
Erstellen Sie eine Ergebnismatrix und setzen Sie alle Werte auf 1. Gehen Sie die Datenmatrix durch, sobald eine 0 auftritt, und setzen Sie die Spalte der Ergebnismatrixzeile auf 0
Am Ende des ersten Durchgangs hat die Ergebnismatrix die richtige Antwort.
Sieht ziemlich einfach aus. Gibt es einen Trick, den ich vermisse? Dürfen Sie keine Ergebnismenge verwenden?
BEARBEITEN:
Sieht aus wie eine F # -Funktion, aber das ist ein bisschen betrügerisch, da die Funktion rekursiv sein kann, obwohl Sie einen einzelnen Durchgang ausführen.
Es sieht so aus, als würde der Interviewer herausfinden, ob Sie mit funktionaler Programmierung vertraut sind.
quelle
Nun, ich habe eine In-Place-Lösung mit einem Durchgang (nicht rekursiv) mit 4 Bools und 2 Schleifenzählern entwickelt. Ich habe es nicht geschafft, es auf 2 Bools und 2 Ints zu reduzieren, aber ich wäre nicht überrascht, wenn es möglich wäre. Es werden ungefähr 3 Lese- und 3 Schreibvorgänge für jede Zelle ausgeführt, und es sollte O (N ^ 2) sein, d. H. linear in der Arraygröße.
Ich habe ein paar Stunden gebraucht, um dieses Problem zu lösen - ich möchte nicht unter dem Druck eines Interviews darauf kommen müssen! Wenn ich einen Booboo gemacht habe, bin ich zu müde, um ihn zu erkennen ...
Ähm ... Ich definiere "Single-Pass" als einen Durchlauf durch die Matrix, anstatt jeden Wert einmal zu berühren! :-)
quelle
Ich hoffe, Ihnen gefällt meine 1-Pass-C # -Lösung
Sie können ein Element mit O (1) abrufen und benötigen nur den Platz einer Zeile und einer Spalte der Matrix
quelle
1 Durchgang, 2 Boolesche Werte. Ich muss nur annehmen, dass die Ganzzahlindizes in den Iterationen nicht zählen.
Dies ist keine vollständige Lösung, aber ich kann diesen Punkt nicht bestehen.
Wenn ich nur feststellen könnte, ob eine 0 eine ursprüngliche 0 oder eine 1 ist, die in eine 0 konvertiert wurde, müsste ich keine -1 verwenden, und das würde funktionieren.
Meine Ausgabe ist wie folgt:
Die Originalität meines Ansatzes besteht darin, anhand der ersten Hälfte der Prüfung einer Zeile oder Spalte festzustellen, ob sie eine 0 enthält, und anhand der letzten Hälfte, um die Werte festzulegen. Dazu werden x und width-x sowie dann y und height betrachtet -y in jeder Iteration. Basierend auf den Ergebnissen der ersten Hälfte der Iteration verwende ich die letzte Hälfte der Iteration, um die Einsen in -1 zu ändern, wenn eine 0 in der Zeile oder Spalte gefunden wurde.
Ich habe gerade festgestellt, dass dies mit nur 1 Booleschen Wert möglich ist und 1 bis ... übrig bleibt.
Ich poste dies in der Hoffnung, dass jemand sagen könnte: "Ah, mach das einfach ..." (Und ich habe viel zu viel Zeit damit verbracht, es nicht zu posten.)
Hier ist der Code in VB:
quelle
Niemand benutzt binäre Formen? da es nur 1 und 0 ist. Wir können binäre Vektoren verwenden.
Hier ist der Test:
Und die Ausgabe:
quelle
Sie können so etwas tun, um einen Durchgang, aber eine Eingabe- und Ausgabematrix zu verwenden:
wo
col(xy)
ist das Bits in der Spalte , die den Punkt enthältxy
;row(xy)
sind die Bits in der Zeile, die den Punkt enthaltenxy
.n
ist die Größe der Matrix.Dann einfach den Eingang durchlaufen. Möglicherweise erweiterbar, um platzsparender zu sein?
quelle
Ein Matrix-Scan, zwei Boolesche Werte, keine Rekursion.
Wie vermeide ich den zweiten Durchgang? Der zweite Durchgang wird benötigt, um die Zeilen oder Spalten zu löschen, wenn die Null am Ende erscheint.
Dieses Problem kann jedoch gelöst werden, da wir beim Scannen der Zeile #i bereits den Zeilenstatus für die Zeile # i-1 kennen. Während wir also die Zeile #i scannen, können wir gleichzeitig die Zeile # i-1 löschen, wenn dies erforderlich ist.
Die gleiche Lösung funktioniert für Spalten, aber wir müssen Zeilen und Spalten gleichzeitig scannen, während die Daten bei der nächsten Iteration nicht geändert werden.
Zum Speichern des Status der ersten Zeile und der ersten Spalte sind zwei Boolesche Werte erforderlich, da ihre Werte während der Ausführung des Hauptteils des Algorithmus geändert werden.
Um das Hinzufügen weiterer Boolescher Werte zu vermeiden, speichern wir das "clear" -Flag für die Zeilen und Spalten in der ersten Zeile und Spalte der Matrix.
quelle
Folgendes scheint ohne zusätzlichen Platzbedarf zu funktionieren:
Beachten Sie zunächst, dass das Multiplizieren der Elemente der Zeile mit den Elementen der Zeile, in der sich ein Element befindet, den gewünschten Wert ergibt.
Um keinen zusätzlichen Speicherplatz zu verwenden (keine neue Matrix erstellen und auffüllen, sondern Änderungen direkt auf die Matrix anwenden), beginnen Sie oben links in der Matrix und führen Sie die Berechnung für eine ixi-Matrix durch (die bei (0 "" beginnt ") , 0)) bevor ein Element mit einem Index> i betrachtet wird.
hoffe das funktioniert (havent testet)
quelle
Dies ist für verschiedene N in C ++ getestet und ist:
EIN PASS , ZWEI BOOLS , KEINE REKURSION , KEIN ZUSÄTZLICHER SPEICHER , HÄLT FÜR ARBITRAR GROSSES N.
(Bisher macht keine der Lösungen hier ALLE diese.)
Genauer gesagt, ich amüsiere mich, dass zwei Schleifenzähler in Ordnung sind. Ich habe zwei nicht signierte Konstanten, die nur existieren und nicht jedes Mal zur besseren Lesbarkeit berechnet werden. Das Intervall der äußeren Schleife ist [0, N] und das Intervall der inneren Schleife ist [1, n - 1]. Die switch-Anweisung ist in der Schleife meistens vorhanden, um sehr deutlich zu zeigen, dass es sich wirklich nur um einen Durchgang handelt.
Algorithmusstrategie:
Der erste Trick besteht darin, eine Zeile und eine Spalte aus der Matrix selbst zu erstellen, um den Inhalt der Matrix zu akkumulieren. Dieser Speicher wird verfügbar, indem alles, was wir wirklich wissen müssen, aus der ersten Zeile und Spalte in zwei Boolesche Werte verschoben wird. Der zweite Trick besteht darin, zwei Durchgänge aus einem herauszuholen, indem die Symmetrie der Submatrix und ihrer Indizes verwendet wird.
Algorithmus Synopsis:
Templatisierte C ++ - Implementierung:
quelle
Ok, mir ist klar, dass es kein gutes Spiel ist, aber ich habe es in einem Durchgang mit einem Bool und einem Byte anstelle von zwei Bools bekommen ... schließen. Ich würde auch nicht für die Effizienz bürgen, aber diese Art von Fragen erfordern oft weniger als optimale Lösungen.
quelle
Sie können dies in einem Durchgang sortieren - wenn Sie den Zugriff auf die Matrix nicht in der Reihenfolge des wahlfreien Zugriffs zählen, wodurch die Vorteile eines einzelnen Durchgangs (Cache-Kohärenz / Speicherbandbreite) entfallen.
[bearbeiten: einfache, aber falsche Lösung gelöscht]
Sie sollten eine bessere Leistung als jede Methode mit einem Durchgang erzielen, indem Sie dies in zwei Durchgängen tun: einem zum Sammeln von Zeilen- / Spalteninformationen und einem zum Anwenden. Auf das Array (in Zeilen-Hauptreihenfolge) wird kohärent zugegriffen; Bei Arrays, die die Cache-Größe überschreiten (deren Zeilen jedoch in den Cache passen), sollten Daten zweimal aus dem Speicher gelesen und einmal gespeichert werden:
quelle
Die einfachste Lösung, die ich mir vorstellen kann, wird unten eingefügt. Die Logik besteht darin, aufzuzeichnen, welche Zeile und Spalte während der Iteration auf Null gesetzt werden soll.
quelle
Hier ist meine Ruby-Implementierung mit dem Test enthalten. Dies würde O (MN) Speicherplatz beanspruchen. Wenn wir eine Echtzeitaktualisierung wünschen (um die Ergebnisse anzuzeigen, wenn wir Nullen finden, anstatt auf die erste Schleife zum Finden von Nullen zu warten), können wir einfach eine andere Klassenvariable erstellen, wie
@output
und wann immer wir eine Null finden, die wir aktualisieren@output
und nicht@input
.quelle
Der folgende Code erstellt eine Matrix der Größe m, n. Entscheiden Sie zuerst die Abmessungen der Matrix. Ich wollte die Matrix [m] [n] zufällig mit Zahlen zwischen 0 und 10 füllen. Erstellen Sie dann eine weitere Matrix mit denselben Abmessungen und füllen Sie sie mit -1s (endgültige Matrix). Durchlaufen Sie dann die Anfangsmatrix, um festzustellen, ob Sie 0 treffen. Wenn Sie auf Position (x, y) klicken, gehen Sie zur endgültigen Matrix und füllen Sie die Zeile x mit 0s und die Spalte y mit 0s. Lesen Sie am Ende die endgültige Matrix durch. Wenn der Wert -1 (ursprünglicher Wert) ist, kopieren Sie den Wert an derselben Stelle der anfänglichen Matrix nach final.
quelle
Hier ist meine Lösung. Wie Sie dem Code entnehmen können, setzt er bei einer M * N-Matrix die gesamte Zeile auf Null, sobald er eine Null in dieser Zeile überprüft. Die zeitliche Komplexität meiner Lösung beträgt O (M * N). Ich teile die gesamte Klasse, die ein statisch bestücktes Array zum Testen und eine Display-Array-Methode hat, um das Ergebnis in der Konsole zu sehen.
}}
quelle