資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究陣列元素頻率範圍查詢的 JavaScript 程式
給定一個包含整數的陣列，以及另一個包含查詢的陣列，每個查詢表示給定的範圍，由陣列中的最左端和最右端索引以及一個元素表示。對於該範圍或子陣列，我們必須找到該範圍內給定元素的頻率。
元素的頻率是指我們需要說明該範圍內每個整數出現的次數。例如 -
如果給定陣列為：[5, 2, 5, 3, 1, 5, 2, 2, 5]
查詢陣列為：[[0, 4, 5], [1, 7, 2]]
對於第一個查詢，子陣列為：5, 2, 5, 3 和 1，因此 5 的頻率為 2。
對於第二個查詢，子陣列為 2, 5, 3, 1, 5, 2 和 2，因此 2 的頻率為 3。
方法
為了解決這個問題，我們將遵循以下步驟 -
首先，我們將建立一個單獨的函式，以便為每個查詢呼叫，並將查詢元素作為引數傳遞。
在函式內部，我們將獲取陣列的長度以遍歷它，並建立一個名為 count 的變數來儲存給定元素的頻率。
我們將使用 for 迴圈遍歷給定的範圍，並在每次迭代中，如果當前陣列元素等於給定元素，則我們將增加計數。
最後，我們將列印給定元素的當前計數。
示例
讓我們看看實現上述步驟的正確程式碼，以便更好地理解 -
// function to answer their queries
function findFre(arr, L, R, ele ){
var n = arr.length
var count = 0
// traversing over the array
for(var i = L; i <= R; i++){
if(arr[i] == ele){
count++;
}
}
console.log("The frequency of the " + ele + " in the range " + L + " to " + R + " is: " + count);
}
// defining array
var arr = [5, 2, 5, 3, 1, 5, 2, 2, 5]
console.log("arr =", arr)
var queries = [[0, 4, 5], [1, 7, 2]]
console.log("queries =", queries)
// traversing over the queries array
for(var i = 0; i<queries.length; i++){
findFre(arr, queries[i][0], queries[i][1], queries[i][2]);
}
時間和空間複雜度
上述程式碼的時間複雜度為 O(Q*N)，其中 Q 是查詢數，N 是陣列的大小。時間複雜度是 N 的因素，因為我們正在遍歷給定範圍內的陣列，對於每個查詢。
上述程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間來儲存任何內容。
特殊情況
在上述程式碼中，我們得到了 O(Q*N) 的時間複雜度，如果給定陣列中存在的不同元素的數量較少，則可以透過犧牲空間複雜度來改進，因為對於每個元素，可以維護一個單獨的陣列或對映以進行字首和。
但是，此方法將佔用大量空間，這將是 O(D*N)，其中 D 是陣列中存在不同元素的數量，N 是陣列的長度。
透過維護字首和，可以在 O(1) 時間內給出任何查詢的答案，並且整體時間複雜度將為 O(Q)，其中 Q 是查詢數。
示例
var store = null;
function lb(a, l, h, k){
if (l > h){
return l;
}
var m = l + parseInt((h - l) / 2);
if (k <= a[m]) {
return lb(a, l, m - 1, k);
}
return lb(a, m + 1, h, k);
}
function ub(a, l, h, k){
if (l > h || l == a.length){
return l;
}
var m = l + parseInt((h - l) / 2);
if (k >= a[m]){
return ub(a, m + 1, h, k);
}
return ub(a, l, m - 1, k);
}
function findFre(arr, L, R, ele){
var n = arr.length
var left_side = lb(store.get(ele), 0, store.get(ele).length, L);
var right_side = ub(store.get(ele), 0, store.get(ele).length, R);
var count = right_side - left_side;
console.log("The frequency of the " + ele + " in the range " + L + " to " + R + " is: " + count);
}
// defining array
var arr = [5, 2, 5, 3, 1, 5, 2, 2, 5]
console.log("arr =", arr)
// creating a map to store the elements
store = new Map();
for (var i = 0; i < arr.length; i++){
if (!store.has(arr[i])){
store.set(arr[i],new Array());
}
store.get(arr[i]).push(i);
}
// creating map for the different elements
// defining queries array
var queries = [[0, 4, 5], [1, 7, 2]]
console.log("queries =", queries)
// traversing over the queries array
for(var i = 0; i<queries.length; i++){
findFre(arr, queries[i][0], queries[i][1], queries[i][2]);
}
結論
在本教程中，我們實現了一個 JavaScript 程式來回答範圍查詢，以回答每個查詢中提供的範圍內給定元素的頻率。我們遍歷了陣列中的給定範圍，並維護了一個變數來獲取計數。上述程式碼的時間複雜度為 O(Q*N)，上述程式碼的空間複雜度為 O(1)。
111 次瀏覽
