c++ - 如何从排序 map 中获取中值

Question

我正在使用 std::map。有时我会做这样的操作:求所有项目的中值。例如如果我添加

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

那么中位数是3。

是否有一些解决方案无需迭代 map 中一半以上的项目？

Answer 1

我认为你可以通过使用两个std::map 来解决这个问题。一个用于较小的一半项目(mapL)，第二个用于另一半(mapU)。当你有插入操作时。这将是任何一种情况:

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

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

上述使用场景仅用于插入，但您也可以将其扩展到删除项目，但您必须跟踪哪个 map 包含项目或尝试从两者中删除。

这是我的代码和示例用法:

#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;
    }
}