[leetCode]剑指 Offer 41. 数据流中的中位数
程序员文章站
2024-02-13 14:04:52
...
最大堆,最小堆
由于需要使用一个数据容器保存从数据流中得到的数据,那么对该容器插入数据与读取数据的时间复杂度有一定要求。
假设数据在容器中已排序,那么使用两个指针即可得到中位数,当数据量为奇数时p1,p2指向同一个数据。
如果数据量为偶数,p1指向左边最大数,p2指向右边最小数。
因此可以将数据分为两部分:
- 左半部分
- 右半部分
左半部分应小于等于右半部分。由于需要快速找到左半部分的最大数与右半部分的最小数,可以想到使用最大堆与最小堆。由于要保证左右两部分数据量之差不超过1,所以可以在数据总量为偶数时将新数据插入最小堆,数据总量为奇数时将数据插入最大堆。
如果新插入最小堆的数据比最大堆的最大数据要小。因为最小堆数据要大于最大堆数据,所以需要新数据插入最大堆,将最大堆的最大数据插入最小堆。同理新插入最大堆的数据大于最小堆最小数据时,应将新数据插入最小堆,将最小堆最小数据插入最大堆。
代码如下:
class MedianFinder {
private PriorityQueue<Integer> minPQ;
private PriorityQueue<Integer> maxPQ;
/** initialize your data structure here. */
public MedianFinder() {
this.minPQ = new PriorityQueue<>(600);//初始化容量
this.maxPQ = new PriorityQueue<>(600,new Comparator<Integer>(){
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
}
public void addNum(int num) {
if(((minPQ.size() + maxPQ.size()) & 1) == 0){//数据总量为偶数,把新数据插入最小堆
if(maxPQ.size() > 0 && num < maxPQ.peek()){//最小堆的数据>最大堆数据
maxPQ.offer(num);//新数据插入最大堆
num = maxPQ.poll();
}
minPQ.offer(num);//取出最大堆最大数据加入最小堆
}else{//数据总量为奇数插入最大堆
if(minPQ.size() > 0 && num > minPQ.peek()){
minPQ.offer(num);
num = minPQ.poll();
}
maxPQ.offer(num);
}
}
public double findMedian() {
int size = minPQ.size() + maxPQ.size();
if(size == 0)
throw new RuntimeException("No numbers are available");
double median = 0;
if((size & 1) == 1)
median = minPQ.peek();
else
median = (minPQ.peek() + maxPQ.peek())/2.0;
return median;
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
推荐阅读
-
python--剑指offer--困难--41. 数据流中的中位数
-
[leetCode]剑指 Offer 41. 数据流中的中位数
-
(python version) 剑指 offer 41. 数据流中的中位数
-
【剑指 Offer 】41. 数据流中的中位数
-
LeetCode 剑指 Offer 41. 数据流中的中位数—— JavaScript
-
《剑指offer》刷题笔记(树):数据流中的中位数
-
DHU高级程序设计-leetcode刷题剑指 Offer 57 - II. 和为s的连续正数序列
-
剑指offer:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
-
剑指offer:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
-
【输入一个整数,输出该数二进制表示中1的个数,其中负数用补码表示---------【剑指offer】】