c++ - 查找多重集中小于或等于 k ​​的元素数

Question

我有一个多重集，实现如下:

#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 解决方案(显然无法编译，因为 multimap 迭代器是双向迭代器，未实现 operator-), 你可以使用 std::distance获取两个 multimap 迭代器之间的距离以获得正确的解决方案。

请注意，此解决方案的复杂度为 O(n)，因为如果迭代器不是随机访问迭代器，std::distance 只会增加传递的迭代器in 作为第一个参数，直到找到作为第二个参数传入的迭代器。

我也不认为这个问题可以用 std::multiset 以比 O(n) 复杂度更好的方式解决。