如何从有序地图中获取中值

Question

我正在使用std :: map.有时我会做一个操作:找到所有项目的中值.例如,如果我添加

1 "s"
2 "sdf"
3 "sdfb"
4 "njw"
5 "loo"

那么中位数是3.

是否有一些解决方案没有迭代地图中的一半以上的项目？

Answer 1

我认为答案是肯定的.您不能只是跳过开头的N/2项,因为它std::map使用双向迭代器.您必须遍历地图中的一半项目.如果您可以访问通常用于的底层红/黑树实现std::map,那么您可以像Dani的答案一样接近.但是,您无权访问它,因为它被封装为实现细节.

Answer 2

我认为你可以用两个来解决这个问题std::map.一个用于较小的一半项目(mapL),另一个用于另一半(mapU).当你有插入操作.它将是这两种情况:

• 将项添加到mapU并将最小元素移动到mapL
• 将项添加到mapL并将最大元素移动到mapU

如果地图具有不同的大小,并且您将元素插入到具有较少元素数的元素,则跳过移动部分.基本思路是保持地图平衡,因此最大尺寸差异为1个元素.据我所知STL所有操作都应该在O(ln(n))时间内工作.可以使用迭代器来访问映射中最小和最大的元素.当你有第n个位置查询时,只需检查地图大小并返回mapL中的最大元素或mapR中的最小元素.

上面的使用场景仅用于插入,但您可以将其扩展为删除项目,但您必须跟踪哪个地图包含项目或尝试从两者中删除.

这是我的代码用例:

#include <iostream>
#include <string>
#include <map>
using namespace std;

typedef pair<int,string> pis;
typedef map<int,string>::iterator itis;

map<int,string>Left;
map<int,string>Right;

itis get_last(map<int,string> &m){
    return (--m.end());
}

int add_element(int key, string val){
    if (Left.empty()){
        Left.insert(make_pair(key,val));
        return 1;
    }

    pis maxl = *get_last(Left);
    if (key <= maxl.first){
        Left.insert(make_pair(key,val));
        if (Left.size() > Right.size() + 1){
            itis to_rem = get_last(Left);
            pis cpy = *to_rem;
            Left.erase(to_rem);
            Right.insert(cpy);
        }
        return 1;
    } else {
        Right.insert(make_pair(key,val));
        if (Right.size() > Left.size()){
            itis to_rem = Right.begin();
            pis cpy = *to_rem;
            Right.erase(to_rem);
            Left.insert(*to_rem);
        }
        return 2;
    }   
}

pis get_mid(){
    int size = Left.size() + Right.size();
    if (Left.size() >= size / 2){
        return *(get_last(Left));
    }
    return *(Right.begin());
}

int main(){
    Left.clear();
    Right.clear();

    int key;
    string val;
    while (!cin.eof()){
        cin >> key >> val;
        add_element(key,val);
        pis mid = get_mid();
        cout << "mid " << mid.first << " " << mid.second << endl;
    }
}