Как найти частоту данного числа в диапазоне в массив?
Проблема в:
Вам дан массив размера 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?
Каково эффективное решение этой проблемы?
Решение
Вы можете решить задачу, используя SQRT-декомпозицию запросов. Сложность будет
Вывода (м * SQRT (п)). Прежде всего, сортируйте все запросы по следующим критериям: 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-декомпозиции запросов вы можете прочитать здесь: ССЫЛКА НА САЙТ
Другие решения
Чтобы очистить карту, нужно позвонить 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) для каждого запроса. Вам просто нужно отсортировать все числа во входном массиве, запомнив их исходные позиции (и убедившись, что сортировка стабильна, чтобы исходные позиции были в порядке возрастания); Вы можете сделать это только один раз. После этого каждый запрос может быть решен с помощью двух бинарных поисков.
Многие алгоритмы доступны для такого рода проблем. Это похоже на прямую проблему структуры данных. Вы можете использовать Сегментное дерево, Разложение квадратного корня. Проверьте Geeksforgeeks на алгоритм! Причина, по которой я говорю вам изучить алгоритм, заключается в том, что проблемы такого рода имеют такие большие ограничения, что ваш вердикт будет TLE, если вы будете использовать свой метод. Так что лучше использовать Алгоритмы.
Многие ответы здесь очень сложны. Я собираюсь рассказать вам простой способ найти диапазон частот. Вы можете использовать метод бинарного поиска, чтобы получить ответ в 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)