資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學JavaScript區間最小公倍數查詢程式
LCM代表最小公倍數，一組數字的最小公倍數是在所有能被該組所有數字整除的數字中，最小的一個。我們將看到完整的程式碼以及對給定問題的解釋。在本文中，我們將實現用於區間LCM查詢的JavaScript程式。
問題介紹
在這個問題中，我們得到一個包含整數的陣列和另一個包含成對數字的查詢陣列，這些數字表示來自給定陣列的範圍，我們必須計算該給定範圍的所有元素的LCM。例如：
如果給定陣列是：[1, 2, 3, 4, 5, 6]，而查詢陣列是：[[1,3], [2,5]]，則對於第一個查詢，元素為[2, 3, 4]，LCM為12。
對於第二個查詢，元素是[3, 4, 5, 6]，LCM是60。
LCM和GCD之間的數學關係
為了找到GCD，我們有一個歐幾里得公式，藉助它我們可以以對數複雜度找到兩個數字的GCD，並且LCM和GCD之間存在以下關係：
LCM and GCD of a given set A {a1, a2, a3 …. , an} is:
LCM(A) * GCD(A) = (a1 * a2 * a3* … * an)
OR
LCM(A) = (a1 * a2 * a3 … * an) / GCD(A)
因此，我們將找到所有數字的GCD和乘積，然後從中，我們可以用O(1)的操作找到數字的LCM。
樸素方法
樸素方法是遍歷查詢陣列，對於每個查詢，找到給定範圍內的元素的乘積和GCD。從這兩個值中找到LCM並返回它。讓我們在程式碼中實現它：
示例
// function to find the gcd of the given number
function gcd(a,b){
if (a == 0) {
return b;
}
else {
return gcd(b%a,a);
}
}
// function to find the lcm
function lcmRange(arr, l, r){
// taking gcd as zero because gcd of 0 with any number is that same number
var cur_gcd = 0
var product = 1
var cur_lcm = arr[l]
for(var i = l+1 ;i <= r; i++) {
product = cur_lcm * arr[i];
cur_gcd = gcd(cur_lcm, arr[i])
cur_lcm = product/cur_gcd
}
console.log("The LCM of the element in the given range from " + l + " to " + r + " is: " + cur_lcm);
}
// defining the array
var arr = [ 1, 2, 3, 4, 5, 6]
// defining the queries array
var queries = [[1,3], [2,5]]
// traversing over the array
for(var i = 0; i< queries.length; i++){
lcmRange(arr,queries[i][0], queries[i][1])
}
時間和空間複雜度
上述程式碼的時間複雜度為O(Q*N*log(D))，其中Q是查詢的數量，N是陣列中的元素數量，D是陣列中最大的數字。
上述程式碼的空間複雜度為O(1)，因為我們沒有使用任何額外的空間。
在上述程式中，如果查詢的數量等於N，則其時間複雜度大於N2，這使得這種方法效率低下。讓我們看看另一種方法：
線段樹方法
線段樹是一種高階資料結構，用於將問題劃分為多個片段，然後根據2的冪將它們全部連線起來。這需要一些空間，但對於區間查詢，可以在對數時間內產生結果。讓我們看看它的程式碼：
示例
// defining maximum size
var MAX = 1000
// makking tree
var tree = new Array(4*MAX);
// declaring new array
var arr = new Array(MAX);
// function for lcm
function lcm(a, b){
return a*b/gcd(a,b);
}
// function for gcd
function gcd(a, b){
if (a == 0) {
return b
}
else{
return gcd(b%a,a);
}
}
// Function to creata a segment tree
function build(first, last, cur_node){
// base condition
if (first == last){
tree[cur_node] = arr[first];
return;
}
var mid = (first + last)/2
mid = Math.floor(mid);
// creating left and right segments
build(first, mid, 2*cur_node);
build(mid+1, last, 2*cur_node + 1);
// build the parent for current
var lcm_l = tree[2*cur_node];
var lcm_r = tree[2*cur_node+1];
tree[cur_node] = lcm(lcm_l, lcm_r);
}
// Function to make queries for array range
function query(first, last, l, r, cur_node){
// section out of current range
// 1 is safe to return
if (last < l || first > r){
return 1;
}
// complete inside the current segment
if (l <= first && r >= last)
return tree[cur_node];
// partially inside the current segment
var mid = (first+last)/2;
mid = Math.floor(mid)
var lcm_l = query(first, mid, l, r, 2*cur_node);
var lcm_r = query(mid+1, last, l, r, 2*cur_node+1);
return lcm(lcm_l, lcm_r);
}
// defining the array
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[3] = 4;
arr[4] = 5;
arr[5] = 6;
// build the segment tree
build(0, 5, 1);
// defining query array
var queries = [[1,3], [2,5]]
// traversing over the array
for(var i = 0; i< queries.length; i++){
console.log("The LCM of the element in the given range from " + queries[i][0] + " to " + queries[i][1] + " is: " + query(0,5,queries[i][0],queries[i][1],1) );
}
結論
在本教程中，我們實現了一個JavaScript程式來查詢區間LCM查詢。我們看到了兩種方法，一種是時間複雜度為O(Q*N*log(D))的樸素方法，另一種是透過實現時間複雜度為O(Q*log(N))的線段樹。
瀏覽量：119
