题解 | #数据流中的中位数#
数据流中的中位数
http://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1
思路:利用 C++ 的有序容器 set 进行数据存储,并使用一个指针,一直指向中位数的位置。
时间复杂度 ,GetMedian 是 O(1),Insert 是 O(log(n)),因为 set 的插入效率是 O(log(n))。
这个方法,比大根堆好理解些,代码量不大。
题解:
1.因为元素可能出现重复,所以使用 set 的可重复元素的版本,multiset
2.使用 multiset::iterator mid 作为中位数存储指针,需要在 Insert 时候,对其进行维护
3.奇数时, mid 指向中位数, 偶数时, mid 指向 中间两数的左边那个。
4.插入时,如果数据长度原本为奇数,插入后则为偶数。如果插入的数据比原中位数要小,则中位数指针左移一位。(这个可以自己画图理解)
5.如果数据长度原本为偶数,插入后则为奇数。如果插入的数据比原中位数要大,则中位数指针右移一位。(可以自己画图理解)
class Solution {
public:
void Insert(int num)
{
data.insert(num);
//维护中位数指针
if (data.size() == 1) //初始化
mid = data.begin();
else if (data.size() %2 == 0) //偶数
{
if (num < *mid)
mid -- ;
}
else //奇数
{
if (num >= *mid)
mid ++ ;
}
}
double GetMedian()
{
if (data.size() %2 == 0) //偶数
{
auto mid2 = mid;
mid2++; // 中间第二个数
return ((double)*mid + *(mid2)) / 2; //均值
}
else //奇数
{
return *mid;
}
}
private:
multiset<int> data;
multiset<int>::iterator mid;
};