中位数"/>
【打卡】牛客网: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)啊?
更多推荐
【打卡】牛客网:BM48 数据流中的中位数
发布评论