程序员面试金典——解题总结：9.18高难度题18.9随机生成一些数字并传入某个方法。编写一个程序，每当收到新数字时，找出并记录中位数。

#include
#include
#include
#include
#include using namespace std;
/*
问题:随机生成一些数字并传入某个方法。编写一个程序&＃xff0c;每当收到新数字时&＃xff0c;找出并记录中位数。
分析&＃xff1a;题目的意思应该是&＃xff1a;根据随机生成了k个数字之后&＃xff0c;接下来每次再收到新数字时&＃xff0c;找到中位数。简化问题&＃xff1a;寻找中位数&＃xff0c;什么是中位数&＃xff1f;就是数组A排序之后&＃xff0c;假设共有n个数字&＃xff0c;如果n为奇数&＃xff0c;那么A[n/2]即为中位数如果n为偶数&＃xff0c;那么A[n/2 - 1] , A[n/2 - 1]累加之后除以2。假设我事先对之前的随机生成的元素组成的数组A排序&＃xff0c;不妨假设不管n为奇数或者偶数&＃xff0c;寻找的中位数都是A[n/2]&＃xff0c;那么我可以事先取出中间3个数A[n/2 - 1],A[n/2]&＃xff0c;A[n/2&＃43;1]然后用新生成的数字和A[n/2]比较&＃xff0c;如果A[n/2] > 生成的数字&＃xff0c;那么新的中位数直接就是A[n/2 - 1]如果A[n/2] <生成的数字&＃xff0c; A[n/2 &＃43; 1]&＃61; A[n/2]书上解法&＃xff1a;
用两个优先级堆&＃xff0c;大顶堆&＃xff1a;存放小于中位数的值&＃xff0c;小顶堆&＃xff1a;存放大于中位数的值。则大顶堆的对顶是最大值&＃xff0c;小顶堆的对顶是最小值。
如果:大顶堆的大小 > 小顶堆的元素大小&＃xff0c;则大顶堆的堆顶为中位数&＃61; &＃xff0c;则大小顶堆的平均值为中位数。
只需要使得大顶堆的大小>&＃61;小顶堆的大小。
有新元素生成&＃xff0c;如果 新元素 <&＃61; 中位数&＃xff0c;放入大顶堆(即包含较小元素的那一堆)&＃xff1b;> 小
如果插入新元素后&＃xff0c;大顶堆元素个数 >&＃61; 小顶堆元素个数&＃43;2&＃xff0c;说明较小的那一堆元素个数多了&＃xff0c;将大顶堆的对顶移动到小顶堆大顶堆元素个数 <小顶堆元素个数&＃xff0c;将小顶堆的对顶移动到大顶堆输入&＃xff1a;
4(初始元素个数)
1 4 7 10
3(后续生成的新元素个数)
3 2 8
输出:
4.00(后续第一个新元素加入后的中位数&＃xff0c;保留两位小数)
3.50
4.00关键:
1
用两个优先级堆&＃xff0c;大顶堆&＃xff1a;存放小于中位数的值&＃xff0c;小顶堆&＃xff1a;存放大于中位数的值。则大顶堆的对顶是最大值&＃xff0c;小顶堆的对顶是最小值。
如果:大顶堆的大小 > 小顶堆的元素大小&＃xff0c;则大顶堆的堆顶为中位数&＃61; &＃xff0c;则大小顶堆的平均值为中位数。
只需要使得大顶堆的大小>&＃61;小顶堆的大小。
有新元素生成&＃xff0c;如果 新元素 <&＃61; 中位数&＃xff0c;放入大顶堆(即包含较小元素的那一堆)&＃xff1b;> 小
如果插入新元素后&＃xff0c;大顶堆元素个数 >&＃61; 小顶堆元素个数&＃43;2&＃xff0c;说明较小的那一堆元素个数多了&＃xff0c;将大顶堆的对顶移动到小顶堆大顶堆元素个数 <小顶堆元素个数&＃xff0c;将小顶堆的对顶移动到大顶堆
*/
class CompareMax
{
public:bool operator()(const int a ,const int b)const{return a > b ? true : false;}
};class CompareMin
{
public:bool operator()(const int a ,const int b)const{return a };//利用初始的数组产生两个堆&＃xff0c;大顶堆存放较小部分元素&＃xff0c;小顶堆存放较大部分元素&＃xff0c;且满足: 小顶堆元素个数<&＃61; 大顶堆元素个数 <&＃61; 小顶堆元素个数&＃43;1
void generateSet(vector& datas , multiset& maxHeap , multiset& minHeap )
{if(datas.empty()){return;}//初始先排序sort(datas.begin() , datas.end());int size &＃61; datas.size();int middleNum &＃61; (size &＃43; 1) / 2;//将前半段小的放入到大顶堆中for(int i &＃61; 0 ; i }double getMiddleNum(multiset& maxHeap , multiset& minHeap )
{int minSize &＃61; maxHeap.size();int maxSize &＃61; minHeap.size();double originalMiddleNum &＃61; 0;//计算原始中位数&＃xff0c;如果总元素个数是奇数个&＃xff0c;那么原始中位数等于大顶堆的堆顶if( ( (minSize &＃43; maxSize) & 1 ) &＃61;&＃61; 1){originalMiddleNum &＃61; *(maxHeap.begin());}else{originalMiddleNum &＃61; ( *maxHeap.begin() &＃43; *minHeap.begin() ) / 2.0;}return originalMiddleNum;
}//根据输入的新元素&＃xff0c;大顶堆和小顶堆&＃xff0c;生成中位数
double generateMiddleNum(int value, multiset& maxHeap , multiset& minHeap )
{double originalMiddleNum &＃61; getMiddleNum(maxHeap , minHeap);//比较如果&＃xff1a;新元素 <&＃61; 原始中位数&＃xff0c;则插入到大顶堆(即较小部分的那一堆元素中)if( 1.0*value <&＃61; originalMiddleNum ){maxHeap.insert(value);}else{minHeap.insert(value);}//如果大顶堆元素个数 >&＃61; 小顶堆元素个数 &＃43; 2 ,就把大顶堆的堆顶移除&＃xff0c;并插入到小顶堆中int minSize &＃61; maxHeap.size();int maxSize &＃61; minHeap.size();if( minSize >&＃61; maxSize &＃43; 2){int value &＃61; *maxHeap.begin();maxHeap.erase(maxHeap.begin());minHeap.insert(value);}//如果大顶堆元素个数 <小顶堆元素个数&＃xff0c;就把小顶堆的堆顶移除&＃xff0c;并插入到大顶堆中else if(minSize }void process()
{int originalNum , addNum ;vector datas;vector newDatas;int value;multiset maxHeap;multiset minHeap;double middleNum;cout.setf(ios::fixed);cout.precision(2);while(cin >> originalNum ){datas.clear();newDatas.clear();maxHeap.clear();minHeap.clear();for(int i &＃61; 0 ; i > value;datas.push_back(value);}//生成初始的大顶堆和小顶堆generateSet(datas , maxHeap , minHeap);cin >> addNum;for(int i &＃61; 0 ; i > value;//接下来对每次新输入的元素&＃xff0c;生成中位数middleNum &＃61; generateMiddleNum(value , maxHeap , minHeap);cout <}int main(int argc , char* argv[])
{process();getchar();return 0;
}