深圳网站开发建设,网站制作的付款方式,wordpress百度经验,wordpress上传地址#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 堆 求解思路 实现代码 运行结果 共勉 题目链接
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 提示:
-105 num 105 在调用 findMedian 之前数据结构中至少有一个元素 最多 5 * 104 次调用 addNum 和 findMedian 求解思路实现代码运行结果 ⚡ 堆 求解思路
该题目看似简单其实还是比较困难第一次做的小伙伴可以参考官方题解求解该题目我们需要维护俩个优先队列一个是大根堆一个是小根堆每次添加元素的时候如果此时俩个优先队列长度不相等先进小根堆然后弹出小根堆堆顶的元素将弹出的元素放到大根堆中。相反如果此时俩个优先队列长度相等那么先进大根堆弹出堆顶的元素进入小根堆。如果是求解中位数的操作还需要判断此时俩个队列的长度如果不相等直接返回小根堆堆顶的元素如果队列长度相等那就取得俩个堆的堆顶元素然后除2得到结果。有了基本的思路接下来我们就来通过代码来实现一下。 实现代码
class MedianFinder {PriorityQueueInteger maxHeap;PriorityQueueInteger minHeap;public MedianFinder() {maxHeap new PriorityQueueInteger((x, y) - (y - x));minHeap new PriorityQueueInteger();}public void addNum(int num) {if (maxHeap.size() ! minHeap.size()) {minHeap.add(num);maxHeap.add(minHeap.poll());} else {maxHeap.add(num);minHeap.add(maxHeap.poll());}}public double findMedian() {if (maxHeap.size() ! minHeap.size()) {return minHeap.peek();} else {return (maxHeap.peek() minHeap.peek()) / 2.0;}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj new MedianFinder();* obj.addNum(num);* double param_2 obj.findMedian();*/运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
