用於數組元素頻率範圍查詢的 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)。

以上是用於數組元素頻率範圍查詢的 Javascript 程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！