数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
