gpt4 book ai didi

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

转载 作者:搜寻专家 更新时间:2023-10-31 00:30:31 24 4
gpt4 key购买 nike

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

#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 使其发挥作用?

最佳答案

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

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

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

关于c++ - 查找多重集中小于或等于 k ​​的元素数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36656866/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com