Javascript-Programm zum Zählen von Einsen in sortierten Binärarrays

Wir haben zwei Möglichkeiten, 1 in einem sortierten binären Array zu zählen. Die erste besteht darin, das Array zu durchlaufen und die Anzahl der Einsen zu zählen. Die zweite Methode besteht darin, den binären Suchalgorithmus zu verwenden, um das erste Vorkommen von 1 im Array zu finden.

Es ist wichtig zu beachten, dass das Array sortiert werden muss, um diese Methoden verwenden zu können.

In diesem Blogbeitrag besprechen wir ein JavaScript-Programm zum Zählen der Anzahl der Einsen in einem sortierten binären Array. Wir werden uns auch einige Randfälle und Optimierungstechniken ansehen, um das Programm effizienter zu machen.

Problemstellung

Bei einem sortierten binären Array besteht die Aufgabe darin, die Anzahl der Einsen im Array zu zählen. Arrays können beliebig groß sein und ihre Elemente dürfen nur 0 oder 1 sein.

Eintreten

bin_array[] = {0, 0, 0,1,1,1}

Ausgabe

3

Methode 1

Der erste Ansatz, der mir in den Sinn kommt, besteht darin, das Array zu durchlaufen und die Anzahl der Einsen zu zählen.

• Initialisieren Sie eine Zählvariable, um die Zahl im Array zu speichern.

• Durchlaufen Sie das Array und überprüfen Sie jedes Element. Wenn das aktuelle Element gleich 1 ist, erhöhen Sie den Zähler.

Beispiel

Die zeitliche Komplexität dieses Ansatzes beträgt jedoch O(n), wobei n die Größe des Arrays ist, da wir das gesamte Array einmal durchlaufen.

Dies kann optimiert werden, indem die Tatsache ausgenutzt wird, dass das Array sortiert ist.

Methode 2

Um die erste Instanz von 1 in einem Array zu finden, verwenden Sie die binäre Suchmethode. Subtrahieren Sie einfach den Index der ersten 1-Instanz von der Gesamtzahl der Elemente im Array, um die Anzahl der Einsen zu erhalten.

• In dieser Implementierung verwenden wir die binäre Suchtechnik „erstes Vorkommen“, um die erste Instanz von 0 im Array zu finden.

• Die Low- und High-Variablen werden zunächst entsprechend auf den ersten und letzten Index des Arrays gesetzt.

• Die Anzahl der Elemente im Array wird auch als Wert einer Variablen namens firstOne angegeben, die zum Aufzeichnen des Index der ersten Instanz der Zahl 1 verwendet wird.

• Die while-Schleife wird so lange ausgeführt, bis der niedrige Index größer oder gleich dem hohen Index ist. Nach jeder Iteration bestimmen wir den Mittelpunkt des aktuellen Bereichs.

• Wenn das mittlere Element 1 ist, aktualisieren Sie die Variable firstOne und verschieben Sie den hohen Index auf das frühere Element. Wenn das Element am Mittelpunkt 0 ist, verschieben wir den unteren Index auf das nachfolgende Element.

• Nach Abschluss der while-Schleife prüfen wir, ob die erste Variable dem -1-Wert des Arrays entspricht. Wenn dies der Fall ist, bedeutet dies, dass im Array keine 1 vorhanden ist und daher 1 zurückgegeben wird. Wenn nicht, geben Sie firstOne minus arr.length zurück.

Beispiel

Die zeitliche Komplexität dieser Methode beträgt O(log n), was viel effizienter ist als die vorherige Methode.

In diesem Tutorial haben wir ein JavaScript-Programm besprochen, um die Anzahl der Einsen in einem sortierten binären Array zu zählen.

Das obige ist der detaillierte Inhalt vonJavascript-Programm zum Zählen von Einsen in sortierten Binärarrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!