1

问题是：给定一个大小为N的数组。还给定q =查询数；在查询中，您将得到l = 下限，u = 上限和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 的大范围查询，它会是一个糟糕的程序吗？这个问题的有效解决方案是什么？

4

4 回答 4

2

您可以使用查询的 SQRT 分解来解决该任务。复杂度为 O(m*sqrt(n))。首先，根据以下条件对所有查询进行排序：L/sqrt(N) 应该增加，其中 L 是查询的左边界。对于相等的 L/sqrt(N)，R（右边界）也应该增加。N 是查询的数量。然后执行此操作：计算第一个查询的答案。然后，只需将这个查询的边界一一移动到下一个查询的边界。例如，如果排序后的第一个查询是 [2,7]，第二个是 [1, 10]，则向左移动到 1 并减少 a[2] 的频率，增加 a 1的频率. 将右边界从 7 移动到 10。增加 a[8]、a[9] 和 a[10] 的频率。使用您的地图增加和减少频率。这是一项非常复杂的技术，但它允许以非常复杂的方式解决您的任务。您可以在此处阅读有关 SQRT 查询分解的更多信息：链接

于 2015-05-05T16:01:42.643 回答
0

要清除地图，您需要调用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)。

然而，对于一个非常大的数组和许多查询（我猜这个问题来自一些竞争性编程网站，不是吗？），这仍然不够。我想应该有一些允许 O(log N) 查询的数据结构和算法，尽管我现在想不出任何。

UPD：我刚刚意识到数组在您的问题中没有改变。这使它更简单，允许每个查询解决方案的简单 O(log N)。您只需对输入数组中的所有数字进行排序，同时记住它们的原始位置（并确保排序稳定，以便原始位置按升序排列）；你只能这样做一次。在此之后，每个查询都可以通过两次二进制搜索来解决。

于 2015-05-05T15:56:13.467 回答
0

许多算法可用于此类问题。这看起来像一个直截了当的数据结构问题。您可以使用分段树、平方根分解。检查 Geeksforgeeks 的算法！我告诉你学习算法的原因是，这种问题有这么大的约束，如果你用你的方法，你的判决将是TLE。所以更好地使用算法。

于 2015-07-13T18:09:40.947 回答
0

这里的许多答案都非常复杂。我将告诉你找到范围频率的简单方法。您可以使用二进制搜索技术在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)

于 2018-01-28T13:31:56.710 回答