c++ - 处理大型数组时超出时间限制

Question

我正在尝试解决 this question :

As we all know that Varchas is going on. So FOC wants to organise an event called Finding Occurrence.

The task is simple :

Given an array A[1...N] of positive integers. There will be Q queries. In the queries you will be given an integer. You need to find out the frequency of that integer in the given array.

INPUT:

First line of input comprises of integer N, the number of integers in given array. The next line will comprise of N space separated integers. The next line will be Q, number of Queries. The next Q lines will comprise of a single integer whose Occurrence you are supposed to find out.

OUTPUT:

Output single integer for each Query which is the frequency of the given integer.

Constraints:

1<=N<=100000

1<=Q<=100000

0<=A[i]<=1000000

这是我的代码:

#include <iostream>
using namespace std;

int main()
{
    long long n=0;
    cin >> n;
    long long a[1000000];
    for (int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    long long q=0;
    cin >> q;
    while (q--)
    {
        long long temp=0,counter=0;
        cin >> temp;
        for (int k=1;k<=n;k++)
        {
            if (a[k]==temp)
                counter++;
        }
        cout << "\n" << counter;
        temp=0;
        counter=0;
    }
    return 0;
}

但是，我遇到了“超出时间限制”的错误。我怀疑这是由于无法处理数组中的大值造成的。谁能告诉我如何处理如此大的数组？

Answer 1

失败在于算法本身，请注意，对于每个查询，您都会遍历整个数组。有 100,000 个查询和 100,000 个元素。这意味着在更坏的情况下，您要遍历 100,000 * 100,000 个元素 = 10,000,000,000 个元素，这些元素不会及时完成。如果您使用 Big-O notation 分析复杂性，你的算法是 O(nq)，这对于这个问题来说太慢了，因为 n*q 很大。

你应该做的是在进行任何查询之前计算分数，然后存储在一个数组中(这就是给出 A[i] 范围的原因。你应该可以通过仅一次遍历数组来做到这一点。(提示:您不需要将输入存储到数组中，您可以直接计数)。

通过这样做，算法将只是 O(n)，并且由于 n 足够小(根据经验，小于一百万是小的), 它应该按时完成。

然后您可以立即回答每个查询，使您的程序足够快，不超过时间限制。

您可以改进的另一件事是数组的数据类型。存储在该数组中的值不会大于 100 万，因此您不需要使用更多内存的 long long。您可以只使用 int。