数组的逆时针旋转意味着将给定数组的所有元素向左侧旋转给定的索引数。在本文中,我们将实现一个 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) 的前缀和方法。
Atas ialah kandungan terperinci Program JavaScript untuk pertanyaan jumlah julat yang memutar tatasusunan mengikut lawan jam oleh indeks K. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!