Как найти частоту данного числа в диапазоне в массив?

Question

Проблема в том, что вам дан массив размером 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;
}

Но у моего кода есть проблема: в каждом запросе карта не становится пустой. Вот почему, если я запрашиваю одно и то же число дважды / трижды, это добавляет счетчик частоты к предыдущему сохраненному.

Как мне это решить? Будет ли это плохая программа для большого диапазона запросов, например 10^5? Каково эффективное решение этой проблемы?

Answer 1

Вы можете решить задачу, используя SQRT-декомпозицию запросов. Сложность будет O(m*sqrt(n)). Прежде всего, сортируйте все запросы по следующим критериям: L/sqrt(N) должно увеличиваться, где L - левая граница запроса. Для равных L/sqrt(N), R (правые границы) тоже должен увеличиваться. N - количество запросов. Затем сделайте это: рассчитайте ответ для первого запроса. Затем просто переместите границы этого запроса к границам следующего запроса один за другим. Например, если ваш первый запрос после сортировки - [2,7], а второй - [1, 10], переместите левую границу на 1 и уменьшите частоту [2], увеличьте частоту на 1. Переместите правую границу от 7 до 10. Увеличьте частоту a[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).

Однако для действительно большого массива и большого количества запросов (я полагаю, что проблема возникла на каком-то конкурентном сайте программирования, не так ли?), Этого все равно будет недостаточно. Я предполагаю, что должна быть некоторая структура данных и алгоритм, который учитывает O (log N) запросов, хотя я не могу думать ни о каких прямо сейчас.

UPD: я только что понял, что массив не меняется в вашей проблеме. Это значительно упрощает задачу, позволяя использовать простое O (log N) для каждого запроса. Вам просто нужно отсортировать все числа во входном массиве, запомнив их исходные позиции (и убедившись, что сортировка стабильна, чтобы исходные позиции были в порядке возрастания); Вы можете сделать это только один раз. После этого каждый запрос может быть решен с помощью двух бинарных поисков.

Answer 3

Многие алгоритмы доступны для такого рода проблем. Это похоже на прямую проблему структуры данных. Вы можете использовать Сегментное дерево, Разложение квадратного корня. Проверьте Geeksforgeeks на алгоритм! Причина, по которой я говорю вам изучить алгоритм, заключается в том, что проблемы такого рода имеют такие большие ограничения, что ваш вердикт будет TLE, если вы будете использовать свой метод. Так что лучше использовать Алгоритмы.

Answer 4

Многие ответы здесь очень сложны. Я собираюсь рассказать вам простой способ найти диапазон частот. Вы можете использовать метод бинарного поиска, чтобы получить ответ в O(logn) на запрос.

Для этого используйте массивы vector для хранения значений индекса всех чисел, присутствующих в массиве, а затем используйте lower_bound и upper_bound, предоставляемые C++ STL.

Вот код 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)