資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
