In diesem Tutorial lernen wir, die Inversion von Größe 3 in einem bestimmten Array zu berechnen.
Problemstellung – Wir erhalten ein Array der Länge n, das verschiedene numerische Einträge enthält. Wir müssen die Gesamtzahl der Zahlenpaare der Größe 3 ermitteln, so dass arr[i] > arr[j] > arr[k], wobei I
Hier lernen wir zunächst die Brute-Force-Methode und optimieren dann deren zeitliche und räumliche Komplexität.
Verwenden Sie Brute-Force-Methoden
Beim Brute-Force-Ansatz verwenden wir drei verschachtelte for-Schleifen, um Zählumkehrungen der Größe 3 zu finden. Die erste Schleife iteriert von 1 bis n-2 Elementen und die zweite Schleife iteriert vom i-ten Element bis zum n-1-ten Element. Wenn das vorherige Element größer als das nächste Element ist, durchlaufen Sie das Array und finden Sie das Element, das kleiner als das mittlere Element ist.
Grammatik
Benutzer können die Brute-Force-Methode verwenden, um die Inversion von Größe 3 in einem bestimmten Array zu berechnen, indem sie der folgenden Syntax folgen.
for ( ) {
for ( ) {
if (array[m] > array[n]) {
for (let o = n + 1; o < len; o++) {
if (array[n] > array[o])
cnt++;
}
}
}
}
Nach dem Login kopieren
Algorithmus
Schritt 1 – Iterieren Sie mit einer for-Schleife über die ersten n-2 Elemente.
Schritt 2 – Iterieren Sie mit einer verschachtelten for-Schleife über m+1 bis len-1-Elemente.
Schritt 3 – Überprüfen Sie in der verschachtelten for-Schleife, ob Array[m] größer als Array[n] ist. Wenn ja, iterieren Sie vom n+1. Element bis zum letzten Element.
Schritt 4 – Wenn das Element am oth-ten Index kleiner ist als das Element am n-ten Index, können wir sagen, dass wir ein gültiges invertiertes Paar der Größe 3 gefunden haben und die Variable „cnt“ minus 1 erhöhen.
Schritt 5 – Nachdem alle Iterationen der for-Schleife abgeschlossen sind, geben Sie den Wert von „cnt“ zurück.
Beispiel 1
Im folgenden Beispiel implementieren wir die Brute-Force-Methode, um die Gesamtzahl der Umkehrpaare der Größe 3 zu ermitteln.
Im angegebenen Array kann der Benutzer nur 2 Inversionspaare in der Ausgabe beobachten. Das erste Umkehrpaar ist (10,5,4) und das zweite Umkehrpaar ist (20,5,4).
<html>
<body>
<h3> Using the <i> Brute force approach </i> to Count Inversions of size three in a given array </h3>
<div id = "output"> </div>
<script>
let output = document.getElementById('output');
function InversionCount(array) {
let len = array.length;
let cnt = 0;
for (let m = 0; m < len - 2; m++) {
for (let n = m + 1; n < len - 1; n++) {
if (array[m] > array[n]) {
for (let o = n + 1; o < len; o++) {
if (array[n] > array[o])
cnt++;
}
}
}
}
return cnt;
}
let array = [10, 20, 5, 4, 50, 60, 30, 40];
output.innerHTML += "The count of inversion in the " + array + " is " + InversionCount(array)
</script>
</body>
</html>
Nach dem Login kopieren
Zeitliche und räumliche Komplexität
Zeitkomplexität – Da wir drei verschachtelte for-Schleifen verwenden, beträgt die Zeitkomplexität O(n^3).
Raumkomplexität – Wenn wir konstanten Raum verwenden, ist die Raumkomplexität O(1).
Verwenden Sie zwei verschachtelte for-Schleifen
In dieser Methode verwenden wir zwei verschachtelte Schleifen. Wir ermitteln die Gesamtzahl der kleineren Elemente rechts vom aktuellen Element und die Gesamtzahl der größeren Elemente links. Danach multiplizieren wir die beiden, um die Gesamtzahl der Inversionen für eine bestimmte Zahl zu erhalten.
Grammatik
Benutzer können der folgenden Syntax folgen, um Umkehrungen der Größe 3 in JavaScript mithilfe von zwei verschachtelten Schleifen zu berechnen.
for ( ) {
// find a smaller element on the right
for ()
if (array[m] < array[n])
right++;
// find bigger elements on the left
for ()
if (array[m] > array[n])
left++;
cnt += right * left;
}
Nach dem Login kopieren
Algorithmus
Schritt 1 – Mit einer for-Schleife über n Elemente des Arrays iterieren.
Schritt 2 – Verwenden Sie eine for-Schleife, um alle Elemente rechts vom aktuellen Element zu finden, die kleiner als das aktuelle Element sind.
Schritt 3 – Verwenden Sie die for-Schleife erneut, um alle Elemente links vom aktuellen Element zu finden, die größer als das aktuelle Element sind.
Schritt 4 – Multiplizieren Sie die Werte der linken und rechten Variablen und addieren Sie sie zur Variablen „cnt“.
Beispiel 2
Im folgenden Beispiel verwenden wir zwei verschachtelte Schleifen, um die Gesamtzahl der Umkehrungen der Größe 3 zu ermitteln, wie in der obigen Methode gezeigt. Der Benutzer kann beobachten, dass die Ausgabe dieselbe ist wie bei der ersten Methode.
<html>
<body>
<h3> Using the <i> two nested loops </i> to Count Inversions of size three in a given array </h3>
<div id = "output"> </div>
<script>
let output = document.getElementById('output');
function InversionCount(array) {
let cnt = 0;
let len = array.length;
// Iterate through every element of the array
for (let m = 0; m < len - 1; m++) {
// count all element that are smaller than arr[m] and at the right to it
let right = 0;
for (let n = m - 1; n >= 0; n--)
if (array[m] < array[n])
right++;
// count all element that are greater than arr[m] and at the left to it
let left = 0;
for (let n = m + 1; n < len; n++)
if (array[m] > array[n])
left++;
// multiply left greater and right smaller elements
cnt += right * left;
}
return cnt;
}
let array = [10, 20, 5, 4, 50, 60, 30, 40];
output.innerHTML += "The count of inversion in the " + array + " is " + InversionCount(array)
</script>
</body>
</html>
Nach dem Login kopieren
Zeitliche und räumliche Komplexität
Zeitkomplexität – Da wir zwei verschachtelte Schleifen verwenden, beträgt die Zeitkomplexität der obigen Methode O(n^2).
Raumkomplexität – Wenn wir konstanten Raum verwenden, ist die Raumkomplexität O(1).
Der Benutzer hat zwei Methoden kennengelernt, um Zählumkehrungen der Größe 3 in einem bestimmten Array zu finden. Im ersten Ansatz haben wir das Problem mithilfe eines Brute-Force-Ansatzes gelöst und im zweiten Ansatz haben wir die Lösung weiter optimiert, um die Zeitkomplexität zu reduzieren.
Das obige ist der detaillierte Inhalt vonJavaScript-Programm zur Berechnung der Inversion der Größe 3 in einem bestimmten Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
