如何从排序图获取中值

本文介绍了如何从排序图获取中值的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我使用的是std :: map。有时我会做一个操作，如：找到所有项目的中间值。例如如果我添加 1s 2sdf 3 sdfb 4njw 5loo 解决方案是否有一些解决方案没有迭代地图中的一半项目？ 我想你可以通过使用两个 std :: map 解决问题。一个用于较小的一半项目（mapL），第二个用于另一半（mapU）。当你有插入操作。这将是以下两种情况之一： 向mapU添加项目，并将最小元素移动到mapL add item to mapL并将最大元素移动到mapU 如果地图具有不同的大小， 元素跳过移动部分。 基本思想是你保持你的地图平衡，所以最大大小的差异是1元素。 据我所知，STL所有操作都应该在O（ln（n））时间工作。在map中访问最小和最大的元素可以通过使用迭代器来完成。 当你有n_th个位置查询时，只需检查map尺寸，并返回mapL中的最大元素或mapR中的最小元素。 上面的使用场景是只插入您可以将其扩展到删除项目，但您必须跟踪哪个地图保存项目或尝试从两者删除。 这是我的代码与示例用法： #include< iostream> #include< string> #include< map> using namespace std; typedef pair< int，string> ; 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 ）; 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.first<< < mid.second<< endl } } I am using a std::map. Sometimes I will do an operation like: finding the median value of all items. e.gif I add 1 "s"2 "sdf"3 "sdfb"4 "njw"5 "loo"then the median is 3. Is there some solution without iterating over half the items in the map? 解决方案 I think you can solve the problem by using two std::map. One for smaller half of items (mapL) and second for the other half (mapU). When you have insert operation. It will be either case:add item to mapU and move smallest element to mapLadd item to mapL and move greatest element to mapUIn case the maps have different size and you insert element to the one with smaller number ofelements you skip the move section.The basic idea is that you keep your maps balanced so the maximum size difference is 1 element.As far as I know STL all operations should work in O(ln(n)) time. Accessing smallest and greatest element in map can be done by using iterator.When you have n_th position query just check map sizes and return greatest element in mapL or smallest element in mapR.The above usage scenario is for inserting only but you can extend it to deleting items as well but you have to keep track of which map holds item or try to delete from both.Here is my code with sample usage:#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; }} 这篇关于如何从排序图获取中值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！