题目描述 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值， 那么中位数就是所有数值排序之后位于中间的数值。 如果从数据流中读出偶数个数值， 那么中位数就是所有数值排序之后中间两个数的平均值。 牛客网题目链接：点击这里
VS2010代码：
// Source: http://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=13&tqId=11216&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking // Author: Yang Qiang // Date : 2016-8-14 #include<iostream> #include<vector> using namespace std; ///思路： 插入排序，用一个容器保存输入的数据 class Solution { vector<int> nums; public: void Insert(int num) { if(nums.empty()) { nums.push_back(num); return; } vector<int>::iterator iter=nums.end()-1; while(num<*iter && iter!=nums.begin()) { iter--; } if(iter==nums.begin() && num<*iter) nums.insert(iter, num); else if(iter==nums.end()-1) nums.push_back(num); else nums.insert(iter+1, num); } double GetMedian() { if(nums.size()%2==0) //偶数个 { int mid=nums.size()/2; double result=(nums[mid]+nums[mid-1]); return result/2; } else { int mid=nums.size()/2; return nums[mid]; } } }; //测试用例：[5,2,3,4,1,6,7,0,8] int main() { Solution s1; s1.Insert(5); cout<<double(s1.GetMedian())<<endl; s1.Insert(2); cout<<double(s1.GetMedian())<<endl; s1.Insert(3); cout<<double(s1.GetMedian())<<endl; s1.Insert(4); cout<<double(s1.GetMedian())<<endl; s1.Insert(1); cout<<double(s1.GetMedian())<<endl; s1.Insert(6); cout<<double(s1.GetMedian())<<endl; s1.Insert(7); cout<<double(s1.GetMedian())<<endl; s1.Insert(0); cout<<double(s1.GetMedian())<<endl; s1.Insert(8); cout<<double(s1.GetMedian())<<endl; }/******************************************** * 知识补充【insert】 ********************************************/ /* iterator insert( iterator loc, const TYPE &val ); * void insert( iterator loc, size_type num, const TYPE &val ); * void insert( iterator loc, input_iterator start, input_iterator end ); * * insert() 函数有以下三种用法: * 在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器, * 在指定位置loc前插入num个值为val的元素 * 在指定位置loc前插入区间[start, end)的所有元素 . */
