Eine binäre Matrix ist eine Matrix, die nur aus zwei Zahlen besteht, die, wie der Name schon sagt, 1 und 0 sind. In diesem Artikel gehen wir Codes und entsprechende Erklärungen durch, um die Konzepte besser zu verstehen. In diesem Tutorial schreiben wir ein JavaScript-Programm, um die Menge der Einsen und Nullen in einer bestimmten Binärmatrix zu zählen.
Einführung in das Problem
Bei diesem Problem erhalten wir eine binäre Matrix und müssen die Menge der Zeilen oder Spalten finden, die denselben Wert enthalten. Eine Menge kann ein einzelner Wert sein oder eine beliebige Größe haben, vorausgesetzt, sie enthält identische Elemente aus Zeilen oder Spalten. Zum Beispiel
Wir haben eine binäre Matrix mit zwei Zeilen und drei Spalten, die so aussieht -
1 0 1
0 0 1
Nach dem Login kopieren
Die Anzahl der Sätze von 1 und 0 kann als
berechnet werden
Satz der Größe 1 − Alle Zellen der Matrix sind eigenständige Sätze und es gibt insgesamt 6 Zellen.
Sätze der Größe 2 - Die ersten beiden Spalten der zweiten Zeile haben die gleichen Werte, die zweite und dritte Spalte haben auch die gleichen Werte, es gibt 2 Sätze der Größe 2 mit den gleichen Werten. In der ersten Zeile stehen zwei weitere Einsen, die als Menge betrachtet werden können
Sammlung der Größe 3 – Die maximal mögliche Sammlungsgröße in einer Matrix ist die maximale Größe von Zeilen und Spalten, hier beträgt sie 3. Für die Größe ist jedoch kein Satz mit demselben Wert verfügbar.
Wir haben also 6er-, 3er- und 0er-Sets für die Größen 1, 2 und 3 im Angebot. Letztendlich wird unsere Antwort also 9 sein.
Methode
Im vorherigen Abschnitt haben wir gesehen, dass wir uns nur auf eine bestimmte Zeile oder Spalte konzentrieren müssen, um die Anzahl der darin enthaltenen ähnlichen Elemente zu ermitteln. Außerdem werden wir ein mathematisches Konzept verwenden, um die Anzahl der darin vorhandenen Mengen mit unterschiedlichen Größen zu zählen eine bestimmte Zeile oder Spalte.
Wenn wir zum Beispiel x Gesamtzahl von Einsen in einer Reihe haben, dann ergibt sich die Gesamtzahl der Sätze von Einsen unterschiedlicher Größe von 1 bis x aus Permutationen.
Lassen Sie uns zu diesem Ansatz übergehen –
Zuerst erhalten wir ein Array mit Nullen und Einsen oder die angegebene Binärmatrix.
Wir erstellen eine Funktion, die automatisch die erforderliche Antwort für jede als Parameter übergebene Matrix berechnet und die Antwort als Rückgabewert zurückgibt.
In dieser Funktion durchlaufen wir das Array oder die Binärmatrix zweimal, einmal zeilenweise und ein zweites Mal spaltenweise.
In der for-Schleife verwalten wir zwei Variablen, eine zum Speichern der Anzahl der Einsen und die andere zum Speichern der Anzahl der Nullen.
Nachdem wir eine einzelne Zeile oder Spalte durchlaufen haben, aktualisieren wir die Antwort mithilfe der oben gezeigten Formel und speichern die Antwort in unserer Variablen.
Abschließend geben wir die Antwort zurück, indem wir die Zeile*Spalte daraus entfernen, da wir sie zweimal hinzugefügt haben.
Wir haben die Zeile * Spalte entfernt, da bei der Iteration über die Zeilen der Menge ein einzelner Wert aus zwei Nullen und einer Eins hinzugefügt wird und bei der Iteration über die Spalten noch einmal.
Die chinesische Übersetzung von
Beispiel
lautet:
Beispiel
Sehen wir uns die Umsetzung der oben genannten Schritte an, um die Konzepte besser zu verstehen -
// given variables
var cols = 3; // no of columns
var rows = 2; // no of rows
// function to solve the problem with passed array
function fun(arr) {
// variable to store the final answer
var ans = 0;
// traversing over the rows using for loop
for (var i = 0; i < rows; i++) {
var ones = 0, zeroes = 0;
for ( var j = 0; j < cols; j++) {
if (arr[i][j] == 1)
ones++;
else
zeroes++;
}
// increasing the answer on the basis of current count based on ones
ans = ans + Math.pow(2, ones)-1;
// based on zeros
ans = ans + Math.pow(2, zeroes)-1;
}
//traversing over the columns using for loop
for (var i = 0; i < cols; i++) {
var ones = 0, zeroes = 0;
for ( var j = 0; j < rows; j++) {
if (arr[j][i] == 1)
ones++;
else
zeroes++;
}
//increasing the answer on the basis of current count based on ones
ans = ans + Math.pow(2, ones)-1;
// based on zeros
ans = ans + Math.pow(2, zeroes)-1;
}
return ans - (rows * cols);
}
var arr = [ [ 1, 0, 1 ], [ 0, 1, 0 ] ];
console.log("Total number of the sets in the given binary matrix is: " + fun(arr));
Nach dem Login kopieren
Zeitliche und räumliche Komplexität
Die zeitliche Komplexität des obigen Codes beträgt O(N*N), wobei N die maximale Anzahl von Zeilen und Spalten der gegebenen Matrix ist.
Es wird kein zusätzlicher Speicherplatz verwendet, daher beträgt die Speicherplatzkomplexität des Codes O(1).
Fazit
In diesem Tutorial haben wir gelernt, wie man ein JavaScript-Programm schreibt, das die Anzahl der Sätze von Einsen und Nullen in einer bestimmten Binärmatrix zählt. Eine binäre Matrix ist eine Matrix, die nur zwei Zahlen enthält, die, wie der Name schon sagt, 1 und 0 sind. Der betreffende Code hat die Zeitkomplexität O(N*N) und die Raumkomplexität O(1).
Das obige ist der detaillierte Inhalt vonJavaScript-Programm: Zählen Sie die Anzahl der Sätze von Einsen und Nullen in einer Binärmatrix. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
