用於按 K 索引逆時針旋轉數組的範圍求和查詢的 JavaScript 程序

陣列的逆時針旋轉意味著將給定陣列的所有元素向左側旋轉給定的索引數。在本文中，我們將實作一個 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) 的前綴和方法。

以上是用於按 K 索引逆時針旋轉數組的範圍求和查詢的 JavaScript 程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！