我怎样才能优化这个下面的程序？

Question

给定一个长度为 N 的数组 A。对于任何给定的整数 X，您需要找到一个严格大于 X 的整数 Z，使得 Z 不存在于数组 A 中。您需要最小化Z.

输入：

第一行：两个 space 分隔的整数 N 和 Q，分别表示数组 A 和数组中元素的数量查询数量分别

第二行：N space 个分隔的整数，表示数组元素

下Q行：每行一个整数X

输出：打印 Q 行，每行表示对应查询的答案。

示例输入：

示例输出：

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;
    }
}

Answer 1

您的查询复杂度为 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)))。

我怎样才能优化这个下面的程序？

How can i optimize this below program?

c++

sorting

implementation

data-structures

array-algorithms