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]);
}
Nach dem Login kopieren
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]);
}
Nach dem Login kopieren
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!
