在多集中查找小于或等于k的元素数

Question

我有一个multiset,实现如下:

#include <bits/stdc++.h>
using namespace std;

multiset <int> M;

int numunder(int k){
    /*this function must return the number of elements smaller than or equal to k
    in M (taking multiplicity into account).
    */
}

起初我以为我可以返回M.upper_bound(k)-M.begin()+ 1.不幸的是,我们似乎无法减去这样的指针.我们最终必须实现AVLNodes结构.有没有办法让这个工作利用c ++ std？

Answer 1

密切关注您提出的M.upper_bound(k)-M.begin()+1解决方案(显然无法编译,因为多图迭代器是一个未实现的双向迭代器operator-),您可以使用std :: distance来获取两个多图迭代器之间的距离,以获得正确的解决方案.

请注意,此解决方案将具有O(n)复杂性,因为如果迭代器不是随机访问迭代器,std::distance则只会增加作为第一个参数传入的迭代器,直到它找到作为第二个参数传入的迭代器.

我也不认为这个问题可以解决,而不是O(n)复杂性std::multiset.