JavaScript程式：陣列逆時針旋轉K位後的區間和查詢

---

陣列的逆時針旋轉是指將給定陣列的所有元素向左旋轉給定索引數。在本文中，我們將實現一個JavaScript程式，用於對陣列逆時針旋轉k位後的區間和查詢。

問題介紹

在這個問題中，我們得到一個包含一些整數的陣列，以及另一個包含成對值的陣列。每一對錶示當前查詢所需的旋轉次數，以及旋轉一定次數後給定的區間，我們需要回答該區間內元素的和。例如：

示例1

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

解釋

旋轉次數為3，所以旋轉3次後的陣列為4 5 6 1 2 3。

在區間1到4內，元素為5, 6, 1, 2。因此，總和為14。

示例2

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

解釋

旋轉次數為8，所以旋轉8次後的陣列等同於8 % (陣列長度) 次旋轉，因為在陣列長度次數的旋轉後，相同的陣列再次出現，這意味著8次旋轉等同於2次旋轉。

所以，旋轉8次後的陣列為3 4 5 6 1 2。

在區間0到3內，元素為3, 4, 5, 6。因此，總和為18。

樸素方法

在樸素方法中，我們將簡單地執行查詢陣列中說明的所有步驟。例如，如果給定旋轉陣列，我們將根據給定的次數旋轉陣列元素，然後檢查該區間內元素的和。讓我們看看它的程式碼：

示例

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

時間和空間複雜度

上述程式碼的時間複雜度為O(Q*N)，其中Q是查詢數，N是陣列的大小。

上述程式碼的空間複雜度為O(N)，因為我們建立了一個大小為N的新陣列。

字首和方法

在字首和方法中，我們將建立一個字首和陣列，字首和陣列的每個索引都包含直到當前索引的所有元素的和。讓我們看看它的程式碼：

示例

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

時間和空間複雜度

上述程式碼的時間複雜度為O(Q)，其中Q是查詢數。

上述程式碼的空間複雜度為O(N)，因為我們建立了一個新陣列來儲存陣列元素的字首和。

結論

在本教程中，我們實現了一個JavaScript程式，用於對陣列逆時針旋轉k位後的區間和查詢。陣列的逆時針旋轉是指將給定陣列的所有元素向左旋轉給定索引數。我們實現了兩種方法，第一種是時間複雜度為O(Q*N)的樸素方法，另一種是時間複雜度為O(Q)的字首和方法。