【打卡】牛客网：BM48 数据流中的中位数

中位数"/>

【打卡】牛客网：BM48 数据流中的中位数

资料：

时间复杂度计算：

【非常全面和详细】时间复杂度计算-例题集合_时间复杂度怎么算_大大枫的博客-CSDN博客

数据结构：关于时间复杂度的例题计算_时间复杂度怎么算-CSDN博客

自己写的：

#include <algorithm>
class Solution {
public:// 堆 priority_queue 比较麻烦// vectorvector <double> a;void Insert(int num) {a.push_back(num);sort(a.begin(),a.end());}double GetMedian() { int n = a.size();// 自己的误区：原来a[n/2]在奇数列是中间；在偶数列是靠后的，不是靠前的。if(n % 2 == 1){return a[n / 2];}else {return (a[n / 2] + a[n / 2 - 1]) / 2.00;}}};

模板的：

• 用的是vector<int> val
• 在push时会遍历val，保证val是有序的。

感觉没有用到堆。难道堆就是表示有序的意思？

时间复杂度是O(nlogn)？好像是O(n)啊？