JavaScript-Programm für die Bereichssummenabfrage, um das Array um den K-Index gegen den Uhrzeigersinn zu drehen

Die Drehung eines Arrays gegen den Uhrzeigersinn bedeutet, dass alle Elemente des angegebenen Arrays um die angegebene Anzahl von Indizes nach links gedreht werden. In diesem Artikel implementieren wir ein JavaScript-Programm für eine Bereichssummenabfrage, die ein Array um k Indizes gegen den Uhrzeigersinn dreht.

Einführung in das Problem

In diesem Problem erhalten wir ein Array mit einigen Ganzzahlen und ein weiteres Array mit Werten in Form von Paaren. Jedes Paar gibt die Anzahl der Umdrehungen an, die für die aktuelle Abfrage erforderlich sind. Nach der angegebenen Anzahl von Umdrehungen erhalten wir einen Bereich und müssen die Summe der in diesem angegebenen Bereich vorhandenen Elemente beantworten. Zum Beispiel

Beispiel 1

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

Anleitung

Die Anzahl der Drehungen beträgt 3, sodass die Anordnung nach dreimaliger Drehung 4 5 6 1 2 3 beträgt.

Die Elemente im Bereich 1 bis 4 sind 5, 6, 1 und 2. Daher beträgt die Gesamtzahl 14.

Beispiel 2

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

Anleitung

Die Anzahl der Drehungen beträgt 8, sodass das Array nach 8 Drehungen 8 % (Array-Länge) Drehungen entspricht, da nach der Länge der Array-Drehungen das gleiche Array erneut erscheint, was bedeutet, dass 8 Drehungen 2 Drehungen entsprechen.

Die Anordnung nach 8-maliger Drehung ist also 3 4 5 6 1 2.

In diesem Bereich sind 0 bis 3 Elemente 3, 4, 5 bzw. 6. Daher beträgt die Summe 18.

Naive Methode

Beim einfachen Ansatz führen wir einfach alle unter „Abfragen eines Arrays“ genannten Schritte aus. Es ist beispielsweise gegeben, das Array zu drehen, und dann drehen wir die Array-Elemente eine bestimmte Anzahl von Malen und überprüfen dann die Summe der Elemente im Bereich. Sehen wir uns den Code an -

Beispiel

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

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 zeitliche Komplexität des obigen Codes beträgt O(N), da wir ein neues Array der Größe N erstellen.

Präfixsummenmethode

Bei der Präfixsummenmethode erstellen wir ein Präfixsummenarray und jeder Index des Präfixsummenarrays enthält die Summe aller Elemente bis zum aktuellen Index. Sehen wir uns den Code an -

Beispiel

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(Q), wobei Q die Anzahl der Abfragen ist.

Die zeitliche Komplexität des obigen Codes beträgt O(N), da wir ein neues Array erstellen, um die Präfixsumme der Array-Elemente zu speichern.

Fazit

In diesem Tutorial haben wir ein JavaScript-Programm für eine Bereichssummenabfrage implementiert, die ein Array um den Index k gegen den Uhrzeigersinn dreht. Eine Array-Rotation gegen den Uhrzeigersinn bedeutet, dass alle Elemente des angegebenen Arrays um die angegebene Anzahl von Indizes nach links gedreht werden. Wir haben zunächst zwei Methoden implementiert, eine naive Methode mit einer Zeitkomplexität von O(Q*N) und eine Präfixsummenmethode mit einer Zeitkomplexität von O(Q).

Das obige ist der detaillierte Inhalt vonJavaScript-Programm für die Bereichssummenabfrage, um das Array um den K-Index gegen den Uhrzeigersinn zu drehen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!