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循环在给定范围内遍历，并在每次迭代时，如果当前数组元素等于给定元素，则增加count。
最后，我们将打印给定元素的当前计数。

示例

让我们看一下实现上述步骤的正确代码，以便更好地理解−

// 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]);
}