Javascript-Programm zur Abfrage des Frequenzbereichs von Array-Elementen

Wir erhalten ein Array mit Ganzzahlen und ein weiteres Array mit Abfragen. Jede Abfrage stellt den Bereich dar, den wir durch den Index ganz links und ganz rechts und ein Element im Array angeben. Für diesen Bereich oder dieses Subarray müssen wir die Häufigkeit des Auftretens eines bestimmten Elements in diesem Bereich ermitteln.

Die Häufigkeit eines Elements bedeutet, dass wir jeder im Bereich vorhandenen Ganzzahl mitteilen müssen, wie oft es vorkommt. Zum Beispiel -

Wenn das gegebene Array ist: [5, 2, 5, 3, 1, 5, 2, 2, 5]

Das Abfragearray ist: [[0, 4, 5], [1, 7, 2]]

• Für die erste Abfrage sind die Subarrays: 5, 2, 5, 3, 1, also ist die Häufigkeit von 5 2.

• Für die zweite Abfrage sind die Subarrays 2, 5, 3, 1, 5, 2 und 2, sodass die Häufigkeit von 2 gleich 3 ist.

Methode

Um dieses Problem zu beheben, führen wir die folgenden Schritte aus -

• Zuerst erstellen wir eine separate Funktion, um jede Abfrage aufzurufen und die Abfrageelemente als Parameter zu übergeben.

• Innerhalb der Funktion ermitteln wir die Länge des zu iterierenden Arrays und erstellen eine Variablenanzahl, um die Häufigkeit des angegebenen Elements zu speichern.

• Wir verwenden eine for-Schleife, um den angegebenen Bereich zu durchlaufen, und erhöhen bei jeder Iteration die Anzahl, wenn das aktuelle Array-Element dem angegebenen Element entspricht.

• Abschließend drucken wir die aktuelle Anzahl des angegebenen Elements aus.

Beispiel

Sehen wir uns zum besseren Verständnis den richtigen Code zur Implementierung der oben genannten Schritte an -

// function to answer their queries 
function findFre(arr, L, R, ele ){
   var n = arr.length 
   var count = 0
   // traversing over the array 
   for(var i = L; i <= R; i++){
      if(arr[i] == ele){
         count++;
      }
   }
   console.log("The frequency of the " + ele + " in the range " + L + " to " + R + " is: " + count);
}
// defining array 
var arr = [5, 2, 5, 3, 1, 5, 2, 2, 5]
console.log("arr =", arr)
var queries = [[0, 4, 5], [1, 7, 2]]
console.log("queries =", queries)
// traversing over the queries array
for(var i = 0; i<queries.length; i++){
   findFre(arr, queries[i][0], queries[i][1], queries[i][2]);
}

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(Q*N), wobei Q die Anzahl der Abfragen und N die Array-Größe ist. Die Zeitkomplexität ist ein Faktor von N, da wir für jede Abfrage das Array innerhalb des angegebenen Bereichs durchlaufen.

Die Speicherplatzkomplexität des obigen Codes beträgt O(1), da wir keinen zusätzlichen Speicherplatz zum Speichern von Daten verwenden.

Besondere Umstände

Im obigen Code erhalten wir die Zeitkomplexität von O(Q*N), die durch Berechnung der Raumkomplexität erhalten werden kann, wenn die Anzahl der verschiedenen Elemente im gegebenen Array kleiner ist als die Anzahl eines separaten Arrays für jedes Element Verbessern Sie die Zeitkomplexität oder behalten Sie die Zuordnung von Präfixsummen bei.

Aber diese Methode verbraucht viel Platz und ihre Komplexität beträgt O(D*N), wobei D die Anzahl der verschiedenen im Array vorhandenen Elemente und N die Länge des Arrays ist.

Durch die Beibehaltung der Präfixsumme kann die Antwort auf jede Anfrage in O(1)-Zeit gegeben werden und die Gesamtzeitkomplexität beträgt O(Q), wobei Q die Anzahl der Anfragen ist.

Beispiel

var store = null;
function lb(a, l, h, k){
   if (l > h){
      return l;
   }
   var m = l + parseInt((h - l) / 2);
   if (k <= a[m]) {
      return lb(a, l, m - 1, k);
   }
   return lb(a, m + 1, h, k);
}
function ub(a, l, h, k){
   if (l > h || l == a.length){
      return l;
   }
   var m = l + parseInt((h - l) / 2);
   if (k >= a[m]){
      return ub(a, m + 1, h, k);
   }
   return ub(a, l, m - 1, k);
}
function findFre(arr, L, R, ele){
   var n = arr.length
   var left_side = lb(store.get(ele), 0, store.get(ele).length, L);
   var right_side = ub(store.get(ele), 0, store.get(ele).length, R);
   var count = right_side - left_side;
   console.log("The frequency of the " + ele + " in the range " + L + " to " + R + " is: " + count);
}
// defining array 
var arr = [5, 2, 5, 3, 1, 5, 2, 2, 5]
console.log("arr =", arr)
// creating a map to store the elements 
store = new Map();
for (var i = 0; i < arr.length; i++){
   if (!store.has(arr[i])){
      store.set(arr[i],new Array());
   }
   store.get(arr[i]).push(i);
}
// creating map for the different elements
// defining queries array 
var queries = [[0, 4, 5], [1, 7, 2]]
console.log("queries =", queries)
// traversing over the queries array
for(var i = 0; i<queries.length; i++){
   findFre(arr, queries[i][0], queries[i][1], queries[i][2]);
}

Fazit

In diesem Tutorial haben wir ein JavaScript-Programm zur Beantwortung von Bereichsabfragen implementiert, um die Häufigkeit eines bestimmten Elements in dem in jeder Abfrage bereitgestellten Bereich zu beantworten. Wir haben den angegebenen Bereich im Array durchlaufen und eine Variable gepflegt, um die Anzahl zu ermitteln. Die zeitliche Komplexität des obigen Codes beträgt O(Q*N) und die räumliche Komplexität des obigen Codes beträgt O(1).

Das obige ist der detaillierte Inhalt vonJavascript-Programm zur Abfrage des Frequenzbereichs von Array-Elementen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!