求中位数其实实在维持中位数,给你一个数组vector<int> nums = {2,1,4,5},我们把小于中位数的放到一起,大于中位数的放到一起,这样中间的那个数就是中位数了.
大于中位数的放到小顶堆,小于中位数的放到大顶堆保持两个堆的大小不超过2,因为中位数两边的数肯定相等的或者一边比另一边大1,但是绝对不能大2,否者中位数就不是当前我们定义的2了当堆大小超过1的时候,我们将中位数加入堆大小较小的一方,然后将堆尺寸大的堆顶作为中位数,出堆就行了. /*=============================================================== # Author: ypp #Filetype:c++ source code #Tool: Vim & Gcc ================================================================*/ #include "iostream" #include "queue" using namespace std; int main(int argc, char** argv){ //双堆得到中位数，不需要排序 priority_queue<int, vector<int>, less<int>> great; //大顶堆 priority_queue<int, vector<int>, greater<int>> low;//小顶堆 vector<int> m = {7,8,6,2,1,4,3,5}; int mid = m[0]; for(int i = 1; i < m.size(); i++){ if(m[i] > mid){ //放到小顶堆中 low.push(m[i]); }else{ great.push(m[i]); } if(great.size() + 1 < low.size()){ //将ｍｉｄ移到大顶堆中，小顶堆堆顶当做mid great.push(mid); mid = low.top(); low.pop(); }else if(low.size() + 1 < great.size()){ low.push(mid); mid = great.top(); great.pop(); } } if(low.size() == great.size()){ cout<<"1中位数是 "<<mid; }else if(low.size() > great.size()){ cout<<"2中位数是 "<<(mid + low.top())/2.0<<endl; }else if(low.size() < great.size()){ cout<<"3中位数是 "<<(mid + great.top())/2.0<<endl; } return 0; }
