在多重集中查找小于或等于k的元素数 [英] Finding the number of elements less than or equal to k in a multiset

查看:362
本文介绍了在多重集中查找小于或等于k的元素数的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有一个multiset,实现如下:

I have a multiset, implemented as follows:

#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).
    */
}

upper_bound(k)-M.begin()+ 1。不幸的是,似乎我们不能减去这样的指针。我们最终必须实现AVLNodes结构。有没有办法使用这个工作利用c ++ std?

At first I thought I could just return M.upper_bound(k)-M.begin()+1. Unfortunately it seems we cannot subtract pointers like that. We ended up having to implement an AVLNodes structure. Is there a way to get this to work taking advantage of the c++ std?

推荐答案

紧贴你的建议 M.upper_bound(k)-M.begin()+ 1 解决方案(显然不编译,因为多重映射迭代器是一个双向迭代器,不能实现 - ),您可以使用 std :: distance 以获得两个多重映射迭代器之间的距离,以获得正确的解。

Sticking closely to your proposed M.upper_bound(k)-M.begin()+1 solution (which clearly does not compile, because the multimap iterator is a bidirectional iterator that does not implement operator-), you could use std::distance to get the distance between two multimap iterators to have a correct solution.

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

Note that this solution will have O(n) complexity, because if the iterator is not a random access iterator, std::distance will just increment the iterator passed in as first parameter, until it finds the iterator passed in as second argument.

我也不认为这个问题可以解决优于 O(n)复杂性与 std :: multiset

I also don't really think that this problem can be solved in better than O(n) complexity with std::multiset.

这篇关于在多重集中查找小于或等于k的元素数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆