数据结构与算法——Java实现 37.求数据流中位数——优先级队列实现
这辈子最蠢的想法就是快点长大
—— 24.10.15
295. 数据流的中位数
中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]
的中位数是3
。- 例如
arr = [2,3]
的中位数是(2 + 3) / 2 = 2.5
。实现 MedianFinder 类:
MedianFinder()
初始化MedianFinder
对象。
void addNum(int num)
将数据流中的整数num
添加到数据结构中。
double findMedian()
返回到目前为止所有元素的中位数。与实际答案相差10-5
以内的答案将被接受。示例 1:
输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0] 解释 MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0
自定义分堆算法见文章:
比较器
import java.util.Comparator;
import java.util.PriorityQueue;
public class LeetCode295_2MiddleInDataStream {
// 添加元素
public void addNum(int num) {
if (leftMinHeap.size() == rightMaxHeap.size()){
rightMaxHeap.offer(num);
leftMinHeap.offer(rightMaxHeap.poll());
}else {
leftMinHeap.offer(num);
rightMaxHeap.offer(leftMinHeap.poll());
}
}
// 寻找中位数
public double findMedian() {
if (leftMinHeap.size() == rightMaxHeap.size()){
return (leftMinHeap.peek() + rightMaxHeap.peek()) / 2.0;
}else {
return leftMinHeap.peek();
}
}
// 大顶堆
private PriorityQueue<Integer> leftMinHeap = new PriorityQueue<>(
(a,b) -> Integer.compare(b,a) // 比较器对象Integer的compare方法比较
);
// 小顶堆
private PriorityQueue<Integer> rightMaxHeap = new PriorityQueue<>(
(a,b) -> Integer.compare(a,b) // 比较器对象Integer的compare方法比较
);
public static void main(String[] args) {
// 小顶堆比较器
//Comparator<Integer> cmp = (a, b) -> Integer.compare(a,b);
// 大顶堆比较器
Comparator<Integer> cmp = (a,b) -> Integer.compare(b,a);
int a = 10;
int b = 20;
if(cmp.compare(a, b) > 0){
System.out.println("上浮");
}else {
System.out.println("停止上浮");
}
}
}
通过调用不同对象切换不同的比较器,就可以切换大顶堆和小顶堆的实现
原文地址:https://blog.csdn.net/m0_73983707/article/details/142930476
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!