用對頂堆來維護。一個大根堆，一個小根堆。
大根堆存前一半的數(shù)據(jù)，小根堆存后一半的數(shù)據(jù)。
需要滿足這樣的一個條件：

• 大根堆最大的數(shù)<=小根堆最小的數(shù)
• 大根堆的數(shù)量最多比小根堆的數(shù)量多1，這樣大根堆的堆頂就是中位數(shù)

#include<bits/stdc++.h> using namespace std; int t,id,n; int main(void) {cin>>t;while(t--){cin>>id>>n;printf("%d %d\n",id,(n+1)/2);priority_queue<int>maxv_heap;//存前一半數(shù)據(jù)priority_queue<int,vector<int>,greater<int>> minv_heap;//存后一半數(shù)據(jù)int cnt=0;for(int i=1;i<=n;i++){int x; cin>>x;if(maxv_heap.empty() || x<=maxv_heap.top()) maxv_heap.push(x);else minv_heap.push(x);if(maxv_heap.size()>minv_heap.size()+1) minv_heap.push(maxv_heap.top()),maxv_heap.pop();if(maxv_heap.size()<minv_heap.size())maxv_heap.push(minv_heap.top()),minv_heap.pop();if(i&1){printf("%d ",maxv_heap.top());cnt++;if(cnt&&(cnt%10==0)) puts("");}}if(cnt%10) puts("");}return 0; }

總結

以上是生活随笔為你收集整理的106. 动态中位数【经典 / 对顶堆】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。