Как я могу оптимизировать эту программу ниже? - PullRequest
Новая
       153

Как я могу оптимизировать эту программу ниже?

0 голосов
/ 21 июня 2020

Вам дан массив A длины N. Для любого заданного целого числа X вам нужно найти целое число Z, строго большее, чем X, такое, что Z не присутствует в массиве A. Вам нужно минимизировать значение Z.

INPUT:

Первая строка: два целых числа N и Q, разделенных пробелами, обозначающие количество элементов в массиве A и количество запросов соответственно

Вторая строка: N разделенных пробелами целые числа, обозначающие элементы массива

Следующие Q строк: каждая строка состоит из целого числа X

ВЫВОД: Распечатайте Q строк, каждая строка обозначает ответ на соответствующий запрос.

Пример ввода: 

5 2
2 7 5 9 15
3
9

Пример вывода: 

4
10

Источник - https://www.hackerearth.com/practice/algorithms/sorting/quick-sort/practice-problems/algorithm/yet-to-keep-6f89250c/description/

Мое решение - 

int main()
{
    ll n,q;
    cin>>n>>q;
    map<ll,bool>mp;
    for(ll i=0;i<n;i++)
    {
        ll x;
        cin>>x;
        mp[x]=true;
    }
    while(q--)
    {
        ll x;
        cin>>x;
        x++;
        while(mp[x])
        {
            x++;
        }
        cout<<x<<endl;
    }
}

1 Ответ

1 голос
/ 21 июня 2020

Ваша сложность по запросу O(n)*(Z-X),

вы уже можете уменьшить до O(n)+(Z-X) с помощью: 

ll x;
std::cin >> x;
x++;
auto it = mp.find(x);
if (it != mp.end()) {
    while (it != mp.end() && it->first == x) {
        ++it;
        ++x;
    }
}
std::cout << x << std::endl;

Но я думаю, что построение интервалов при предварительной обработке позволит даже лучшая производительность (O(log(Intervals))).

...