用于按 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中文网其他相关文章！