阿木技术分享 2023-09-06

用于数组元素频率范围查询的 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]);
}

登录后复制