Programme JavaScript pour la requête de somme de plage qui fait pivoter le tableau dans le sens inverse des aiguilles d'une montre par l'index K

La rotation dans le sens inverse des aiguilles d'une montre d'un tableau signifie faire pivoter tous les éléments du tableau donné vers la gauche du nombre d'indices donné. Dans cet article, nous allons implémenter un programme JavaScript pour une requête de somme de plage qui fait pivoter un tableau dans le sens inverse des aiguilles d'une montre de k indices.

Introduction au problème

Dans ce problème, on nous donne un tableau contenant des entiers et un autre tableau contenant des valeurs sous forme de paires. Chaque paire sera le nombre de rotations requis pour la requête en cours, après le nombre de rotations donné, nous obtiendrons une plage et devrons répondre à la somme des éléments présents dans cette plage donnée. Par exemple,

Exemple 1

Input
Given array: [1, 2, 3, 4, 5, 6] 
Query: [3, 1, 4]
Output 14

Instructions

Le nombre de rotations est de 3, donc le tableau après avoir tourné 3 fois est 4 5 6 1 2 3.

Les éléments compris entre 1 et 4 sont 5, 6, 1 et 2. Le total est donc de 14.

Exemple 2

Input
Given array: [1, 2, 3, 4, 5, 6] 
Query: [8, 0, 3]
Output 18

Instructions

Le nombre de rotations est de 8, donc le tableau après 8 rotations est égal à 8 % (longueur du tableau) de rotations, car après la longueur des rotations du tableau, le même tableau apparaît à nouveau, ce qui signifie que 8 rotations sont équivalentes à 2 rotations.

Donc, le tableau après avoir tourné 8 fois est 3 4 5 6 1 2.

Dans cette plage, 0 à 3 éléments font respectivement 3, 4, 5 et 6. La somme est donc 18.

Méthode naïve

Dans l'approche simple, nous effectuerons simplement toutes les étapes indiquées dans Interrogation d'un tableau. Par exemple, il est donné de faire pivoter le tableau, puis nous faisons pivoter les éléments du tableau un nombre de fois donné, puis vérifions la somme des éléments de la plage. Voyons son code -

Exemple

// function to answer the queries 
function getSum(arr, rotations, L, R){
   var len = arr.length 
   var rot = rotations % len;
   var temp = new Array(len);
   
   // rotating the given array
   for(var i =0;  i< len - rot; i++ ){
      temp[i] = arr[i + rot];
   }
   
   // getting the last elements 
   for(var i = 0; i < rot; i++)    {
      temp[len-rot+i] = arr[i];
   }
   
   // getting the required sum
   var sum = 0;
   for(var i = L; i<=R; i++){
      sum += temp[i];
   }
   console.log("The sum of the elements in the range " + L + " to " + R + " after " + rotations + " number of rotations is " + sum);
}

// defining the array 
var arr = [ 1, 2, 3, 4, 5, 6]

// defining the queries array 
var queries = [ [ 3, 1, 4], [ 8, 0, 3]]
 
// traversing over the given array 
for(var i = 0; i<queries.length; i++){
   getSum(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 du code ci-dessus est O(N) car nous créons un nouveau tableau de taille N.

Méthode de somme de préfixe

Dans la méthode de somme de préfixes, nous allons créer un tableau de somme de préfixes et chaque index du tableau de somme de préfixes contient la somme de tous les éléments jusqu'à l'index actuel. Voyons son code -

Exemple

// function to answer the queries 
function getSum(preSum, rotations, L, R){
   var len = preSum.length 
   var rot = rotations % len;
   
   // updating L and R 
   L = (L + rot) %len
   R = (R + rot) %len
   var sum = 0;
   if(L <= R) {
      if(L == 0) {
         sum = preSum[R];
      }
      else{
         sum = preSum[R]-preSum[L-1];
      }
   }
   else{
      sum += preSum[R];
      sum += preSum[len-1]-preSum[L-1];
   }
   console.log("The sum of the elements in the range " + L + " to " + R + " after " + rotations + " number of rotations is " + sum);
}

// defining the array 
var arr = [ 1, 2, 3, 4, 5, 6]
var preSum = new Array(arr.length)
preSum[0] = arr[0]
for(var i = 1; i<arr.length; i++){
   preSum[i] = preSum[i-1] + arr[i]
}

// defining the quries array 
var queries = [ [ 3, 1, 4], [ 8, 0, 3]] 

// traversing over the given array 
for(var i = 0; i<queries.length; i++){
   getSum(preSum, queries[i][0], queries[i][1], queries[i][2]);
}

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(Q), où Q est le nombre de requêtes.

La complexité temporelle du code ci-dessus est O(N) car nous créons un nouveau tableau pour stocker la somme des préfixes des éléments du tableau.

Conclusion

Dans ce didacticiel, nous avons implémenté un programme JavaScript pour une requête de somme de plage qui fait pivoter un tableau dans le sens inverse des aiguilles d'une montre d'un indice k. La rotation du tableau dans le sens inverse des aiguilles d'une montre signifie faire pivoter tous les éléments du tableau donné vers la gauche du nombre d'indices donné. Nous avons d’abord implémenté deux méthodes, une méthode naïve avec une complexité temporelle de O(Q*N) et une méthode de somme de préfixes avec une complexité temporelle de O(Q).

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!