LCM 代表最小公倍數,一組數字的 LCM 是可被給定集合中存在的所有數字整除的所有數字中的最小數字。我們將看到完整的程式碼以及給定問題的解釋。在本文中,我們將為一系列 LCM 查詢實作 JavaScript 程式。
在這個問題中,我們得到一個包含整數的數組和另一個包含表示給定數組範圍的成對數字的數組查詢,我們必須計算該給定範圍內所有元素的 LCM。例如 -
如果給定數組為:[1, 2, 3, 4, 5, 6] 且查詢數組為:[ [1,3], [2,5]] 則第一個查詢元素為[2 , 3, 4]和12是LCM。
對於第二個查詢元素為 [3, 4, 5, 6] LCM 為 60。
為了找到 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,這使得方法使用效率低。讓我們看看這是另一種方法 &miinus;
線段樹是一種高階資料結構,用於將問題分割為多個線段,然後以 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)) 的線段樹實現。 p>
以上是用於範圍 LCM 查詢的 JavaScript 程式的詳細內容。更多資訊請關注PHP中文網其他相關文章!