数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究数组区间乘积的 JavaScript 程序
我们将得到一个数组，并且我们需要回答一些与给定范围相关的查询，即从给定的起始索引到结束点或索引，我们需要返回该范围内元素的乘积。在本文中，我们将看到一些在 JavaScript 中实现上述问题的方法及其解释。
问题介绍
给定一个数组和一些查询，在每个查询中，我们将通过指示范围的第一个和最后一个索引来获得一些范围，我们需要回答该范围内每个元素的乘积。
例如 -
Given array: 1 2 3 4 5 6 the product of range 0 to 2 is: 1 * 2 * 3 = 6. The product of range 2 to 4 is: 3 * 4 * 5 = 60.
我们将看到两种解决问题的方法，第一种是简单的朴素方法，另一种是数学模逆方法。
朴素方法
在这种方法中，我们将简单地遍历数组，并且对于每个查询，我们将维护一个变量来存储乘积。
示例
让我们看看代码 -
// function to find the range’s product
function rangeFun(arr, L, R){
// getting length of the array
var len = arr.length
// variable to maintain the result
var ans = 1
// traversing over the array in the given range
for(var i = L; i <= R; i++) {
ans *= arr[i];
}
console.log("The product of the elements in the given range " + L + " to " + R + " is: " + ans )
}
// defining the array
var arr = [ 1, 2, 3, 4, 5, 6]
// calling the function in the range 0 to 2
rangeFun(arr, 0 ,2)
// calling the function in range 3 to 5
rangeFun(arr, 3 , 5)
时间和空间复杂度
上述代码的时间复杂度为 O(N)，其中 N 是给定数组中元素的数量，上述代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。
在上面的代码中，时间复杂度仅为 O(N)，但问题在于它仅针对单个查询，并且随着查询数量的增加，它呈线性增加，这使得它无法胜任处理 N 个查询的任务。为了解决此问题，我们将使用数学概念模逆。
模乘法逆元
由于 P 是素数，我们可以利用模乘法逆元。我们可以使用动态规划计算模 P 下的预乘积数组，使得索引 i 处的值包含范围 [0, i] 中的乘积。类似地，我们可以确定相对于 P 的预逆乘积。现在每个查询都可以在 O(1) 时间内得到解答。
由于乘积是模 P 计算的，因此我们无法将解计算为 Product[R]/Product[L-1]。如果我们不计算模 P 下的乘积，则始终存在溢出的风险。
示例
让我们看看代码 -
// defining some variable to work with
var max_length = 100;
var preProduct = new Array(max_length);
var inverseProduct = new Array(max_length);
// function to return the modulo inverse
function modInverse(a, m){
var m0 = m, t, q;
var x0 = 0
var x1 = 1
if (m == 1) {
return 0;
}
while (a > 1) {
// here q is the quotient
q = parseInt(a / m, 10);
t = m;
// m is remainder now, process
// same as Euclid's algo
m = a % m;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
// Make x1 positive
if (x1 < 0) {
x1 += m0;
}
return x1;
}
// calculating pre_product of the givne array
function calculate_Pre_Product(arr, n, p){
preProduct[0] = arr[0];
for (var i = 1; i < n; i++) {
preProduct[i] = preProduct[i - 1] * arr[i];
preProduct[i] = preProduct[i] % p;
}
}
// Calculating inverse_product of the given array
function calculate_inverse_product(arr, n, p){
inverseProduct[0] = modInverse(preProduct[0], p);
for (var i = 1; i < n; i++) {
inverseProduct[i] = modInverse(preProduct[i], p);
}
}
// defining the function to calculate Product
// in the given range.
function rangeFun(arr, L, R, p){
var ans = 0;
if (L == 0) {
ans = preProduct[R];
}
else{
ans = preProduct[R] * inverseProduct[L - 1];
}
console.log("The product of the elements in the given range " + L + " to " + R + " is: " + ans )
}
// defining the array
var arr = [ 1, 2, 3, 4, 5, 6 ];
// defining the modulo prime number
var p = 113;
// Calculating PreProduct and InverseProduct
calculate_Pre_Product(arr, arr.length, p);
calculate_inverse_product(arr, arr.length, p);
rangeFun(arr, 0 ,2, p)
rangeFun(arr, 0 , 5, p)
时间和空间复杂度
上述代码的时间复杂度为 O(1)，而上述代码的空间复杂度为 O(N)，因为我们使用两个长度为 N 的数组来存储元素。
结论
在本教程中，我们实现了数组区间乘积的 JavaScript 文章。我们需要回答一些与给定范围相关的查询，为此我们编写了两个程序。第一个程序是时间复杂度为 O(N) 的朴素方法，另一个方法是使用时间复杂度为 O(1) 的模逆概念。
144 次浏览
