我如何找到给定数字的频率到一个数组中的范围

Question

问题是：给您一个大小 n 的数组。还给出了 Q =查询数;在查询中，您将得到 l =较低范围， u = upper范围和 num =您必须将频率计算为l〜u。

我已经在C 中实现了我的代码：

#include <iostream>
#include <map>
using namespace std;
map<int,int>m;
void mapnumbers(int arr[], int l, int u)
{
    for(int i=l; i<u; i++)
    {
        int num=arr[i];
        m[num]++;
    }
}

int main()
{
    int n; //Size of array
    cin>>n;
    int arr[n];
    for(int i=0; i<n; i++)
        cin>>arr[i];
    int q; //Number of queries
    cin>>q;
    while(q--)
    {
        int l,u,num;   //l=lower range, u=upper range, num=the number of which we will count frequency
        cin>>l>>u>>num;
        mapnumbers(arr,l,u);
        cout<<m[num]<<endl;
    }
    return 0;
}

但是我的代码有问题，在每个查询中，它都不会使映射 m 空。这就是为什么如果我查询相同数字两次/三次，则添加了先前存储的频率计数。

我该如何解决？对于10^5的各种查询，这会是一个糟糕的程序吗？什么是这个问题的有效解决方案？

Answer 1

您可以使用查询的SQRT解码来解决任务。复杂性将是o（m*sqrt（n））。首先，由于以下标准，对所有查询进行排序：l/sqrt（n）应增加，其中l是查询的左界。对于相等的l/sqrt（n），r（右边界）也应增加。n是查询的数量。然后执行此操作：计算第一个查询的答案。然后，只需移动此查询的边界与的边界>一个一个查询一个一个。例如，如果您的第一个查询为[2,7]，而第二个是[1，10]，则向左移动至1，并降低A [2]的频率，则会增加A1的频率。将右界限从7移动到10。增加[8]，a [9]和a [10]的频率。使用地图增加和降低频率。这是一项非常复杂的技术，但是它允许以良好的复杂性解决您的任务。您可以在此处阅读有关查询的SQRT解码的更多信息：link

Answer 2

要清除地图，您需要致电map::clear()：

void mapnumbers(int arr[], int l, int u)
{
    m.clear()

解决清除问题的更好方法是使m成为while (q--)循环甚至mapnumbers函数的局部变量。

但是，总的来说，为什么您完全需要地图很奇怪。无论如何，您都会穿越整个数组，并且知道需要计算的数字，所以为什么不这样做

int mapnumbers(int arr[], int l, int u, int num)
{
    int result = 0;
    for(int i=l; i<u; i++)
    {
        if (arr[i] == num);
            result ++;
    }
    return result;
}

这将更快，甚至渐近地更快，因为map操作为O（log n），因此您的原始解决方案每个查询都为O（n log n）运行，而此简单的迭代则用于O（n）。p>但是，对于一个非常大的数组和许多查询（我想问题来自某个竞争性编程网站，不是吗？），这仍然是不够的。我猜应该有一些数据结构和算法可以允许O（log n）查询，尽管我现在无法想到任何。

upd：我刚刚意识到该数组不会改变您的问题。这使其变得更加简单，允许每个查询解决方案一个简单的O（log n）。您只需要对输入阵列中的所有数字进行排序，也需要记住它们的原始位置（并确保排序稳定，以便原始位置的顺序增加）；您只能做一次。之后，只需两个二进制搜索即可解决每个查询。

Answer 3

许多算法可用于此类问题。这看起来像是直截了当的数据结构问题。您可以使用片段树，平方根分解。检查geeksforgeeks中的算法！我告诉您学习算法的原因是，这种问题具有如此大的限制，如果您使用方法，您的判决将是TLE。因此，使用算法更好。

Answer 4

这里的许多答案非常复杂。我将告诉您轻松找到范围频率的方法。您可以使用二进制搜索技术在 o（logn）下获取答案。

为此，使用向量的数组存储数组中存在的所有数字的索引值，然后使用C STL提供的lower_bound和upper_bound。

这是C 代码：

    #define MAX 1000010
    std::vector<int> v[MAX];
    int main(){
    cin>>n;
    for (int i = 0; i < n; ++i)
    {
        cin>>a;
        v[a].push_back(i);
    }
    int low = 0, high = 0;
    int q; //Number of queries
    cin>>q;
    while(q--)
    {
        int l,u,num;   //l=lower range, u=upper range, num=the number of which we will count frequency
        cin>>l>>u>>num;
        low = lower_bound(v[num].begin(), v[num].end(), l) - v[num].begin();
        high = upper_bound(v[num].begin(), v[num].end(), u) - v[num].begin();
        cout<<(high - low)<<endl;
    }
    return 0;
}

总体时间复杂度： O（q*log n）