题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
大顶堆&小顶堆
思路分析
利用堆的知识，一个大顶堆（保存数据流中的前一半数），一个小顶堆（保存数据流中的后一半数）。这样，当数据流为偶数个时，结果为两个堆顶的平均值，当数据流为奇数个时，结果为大顶堆的堆顶。
我们需要维护这两个堆，保证：
- 大顶堆的所有数比小顶堆小
- 保证大顶堆的数量等于小顶堆的数量 或者 大顶堆的数量等于小顶堆的数量+1
代码
因为涉及大顶堆和小顶堆，还是用C++写方便，所以使用C++
class Solution {
public:
priority_queue<int, vector<int>, greater<int>> minHeap;
priority_queue<int, vector<int>, less<int>> maxHeap;
void Insert(int num)
{
//如果大顶堆为空，或数小，优先进大顶堆
if (maxHeap.empty()|| num<=maxHeap.top())
maxHeap.push(num);
else minHeap.push(num);
//奇数个时，保证大顶堆的数量比小顶堆多1
if (minHeap.size() == maxHeap.size()+1)
{
maxHeap.push(minHeap.top());
minHeap.pop();
}
//偶数个时，要维持两个堆的数量均衡
if (minHeap.size() + 2 == maxHeap.size())
{
minHeap.push(maxHeap.top());
maxHeap.pop();
}
}
double GetMedian()
{
if (minHeap.size() == maxHeap.size())
return (minHeap.top()+maxHeap.top())/2.0;
else
return maxHeap.top();
}
};
代码重点分析
- 大顶堆、小顶堆的C++写法
priority_queue<int> q; //C++里默认是大顶堆
priority_queue<int, vector<int>, less<int>> maxHeap; //和上一行等价，大顶堆
priority_queue<int, vector<int>, greater<int>> minHeap; //小顶堆
这里要说明的是，C++里不标明比较逻辑时，默认是大顶堆。而python中q = Queue.PriorityQueue()默认是小顶堆。
其次，C++中的vector<int>不要丢失。
- 精度损失的问题
当数据流为偶数个时，需要算堆顶数据的平均值。
return (minHeap.top()+maxHeap.top())/2;返回的结果是错误的，因为除以了int类型，造成精度损失。所以需要写成/2.0
快排思想，找第k个数
思路分析
使用快排的partition思想，每次确定一个数在序列中的位置，若大于k，则在该数左边的序列中继续找，若大于k，则在该数右边的序列中找。
当数的个数n为奇数时，我需要找到第n/2大的数（从0开始计数）。
当数的个数n为偶数时，我需要找到第n/2-1大的数和第n/2大的数（从0开始计数），取其平均值。
代码
class Solution {
vector<int> numbers;
public:
void Insert(int num){
numbers.push_back(num);
}
int partition(int left, int right){
if (left>=right)
return left;
int lo = left+1, hi = right;
int pivot = numbers[left];
while(lo <= hi){
if (numbers[lo]>pivot)
swap(numbers[lo], numbers[hi--]);
else lo++;
}
swap(numbers[hi], numbers[left]);
return hi;
}
int getNum(int k, int left, int right){
int index = partition(left, right);
while(index != k){
if (index<k){
left = index+1;
index = partition(left, right);
}
else{
right = index-1;
index = partition(left, right);
}
}
return numbers[index];
}
double GetMedian(){
int len = numbers.size();
if (len & 1 != 0) //奇
return (double)getNum(len/2, 0, len-1);
else{
int num1 = getNum(len/2-1, 0, len-1);
int num2 = getNum(len/2, len/2, len-1);
return (num1+num2)/2.0;
}
}
};
代码重点分析
- partition肯定要记牢的，多种场景下用处很大
- 关于时间复杂度的分析
假设，
则
所以时间复杂度为O(n)
参考
讨论区中马客(Mark)的代码
讨论区里还有手写AVL的，太优秀了
