Programme Javascript pour la requête de plage de fréquences d'éléments de tableau

Nous obtenons un tableau contenant des entiers et un autre tableau contenant des requêtes, chaque requête représente la plage que nous donnons par l'index le plus à gauche et le plus à droite et un élément du tableau. Pour cette plage ou ce sous-tableau, nous devons trouver la fréquence d'apparition d'un élément donné dans cette plage.

La fréquence d'un élément signifie que nous devons indiquer à chaque entier présent dans la plage combien de fois il apparaît. Par exemple -

Si, le tableau donné est : [5, 2, 5, 3, 1, 5, 2, 2, 5]

Le tableau de requête est : [[0, 4, 5], [1, 7, 2]]

• Pour la première requête, les sous-tableaux sont : 5, 2, 5, 3, 1, donc la fréquence de 5 est 2.

• Pour la deuxième requête, les sous-tableaux sont 2, 5, 3, 1, 5, 2 et 2, donc la fréquence de 2 est 3.

Méthode

Pour résoudre ce problème, nous suivrons les étapes suivantes -

• Tout d'abord, nous allons créer une fonction distincte pour appeler chaque requête et transmettre les éléments de la requête en tant que paramètres.

• À l'intérieur de la fonction, nous obtiendrons la longueur du tableau à parcourir et créerons un nombre de variables pour stocker la fréquence de l'élément donné.

• Nous utiliserons une boucle for pour parcourir la plage donnée et à chaque itération, si l'élément actuel du tableau est égal à l'élément donné, nous incrémenterons le nombre.

• Enfin, nous imprimerons le nombre actuel de l'élément donné.

Exemple

Voyons le code correct pour mettre en œuvre les étapes ci-dessus pour une meilleure compréhension -

// 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]);
}

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(Q*N), où Q est le nombre de requêtes et N est la taille du tableau. La complexité temporelle est un facteur N car pour chaque requête, nous parcourons le tableau dans la plage donnée.

La complexité spatiale du code ci-dessus est O(1) car nous n'utilisons aucun espace supplémentaire pour stocker quoi que ce soit.

Circonstances particulières

Dans le code ci-dessus, nous avons obtenu la complexité temporelle de O(Q*N), qui peut être obtenue en calculant la complexité spatiale si le nombre d'éléments différents présents dans le tableau donné est inférieur au nombre d'un tableau distinct pour chacun élément Améliorer la complexité temporelle ou maintenir le mappage des sommes de préfixes.

Mais cette méthode consomme beaucoup d'espace et sa complexité est O(D*N), où D est le nombre d'éléments différents présents dans le tableau et N est la longueur du tableau.

En conservant la somme des préfixes, la réponse à n'importe quelle requête peut être donnée en un temps O(1) et la complexité temporelle globale sera O(Q), où Q est le nombre de requêtes.

Exemple

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]);
}

Conclusion

Dans ce tutoriel, nous avons implémenté un programme JavaScript pour répondre aux requêtes de plage afin de répondre à la fréquence d'un élément donné dans la plage fournie dans chaque requête. Nous avons parcouru la plage donnée dans le tableau et conservé une variable pour obtenir le nombre. La complexité temporelle du code ci-dessus est O(Q*N) et la complexité spatiale du code ci-dessus est O(1).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!