湘潭市 网站建设,手机百度屏蔽我网站关键词,二手物品交换网站建设,flash网站代码下载题目链接#xff1a;https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
1. 题目介绍#xff08;41. 数据流中的中位数#xff09; 如何得到一个数据流中的中位数#xff1f;如果从数据流中读出奇数个数值#xff0c;那么中位数就是所有数值排序之后位…题目链接https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
1. 题目介绍41. 数据流中的中位数 如何得到一个数据流中的中位数如果从数据流中读出奇数个数值那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值那么中位数就是所有数值排序之后中间两个数的平均值。 例如 [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 3) / 2 2.5 设计一个支持以下两种操作的数据结构 void addNum(int num) - 从数据流中添加一个整数到数据结构中。double findMedian() - 返回目前所有元素的中位数。 【测试用例】 示例 1 输入 [“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”] [[],[1],[2],[],[3],[]] 输出[null,null,null,1.50000,null,2.00000] 示例 2 输入 [“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”] [[],[2],[],[3],[]] 输出[null,null,2.00000,null,2.50000] 【条件约束】 限制 最多会对 addNum、findMedian 进行 50000 次调用。 【相关题目】 注意本题与主站 295. 数据流的中位数 题目相同。 2. 题解
2.1 最大堆和最小堆原书题解 – O(logn)
时间复杂度O(logn)空间复杂度O(n) 偶数情况 【解题思路】 该题的解法很多可以通过数组、链表、二叉搜索树、AVL树、最大堆和最小堆来实现目前最推荐的就是使用 最大堆和最小堆 来解决该问题。该题可以将整个数据容器分成两部分左边部分的数据要比右边的数据小。我们可以用一个最大堆实现左边的数据容器用一个最小堆实现右边的数据容器。 两个保证 要保证数据平均分配到两个堆中两个堆中数据的数目之差不能超过1;要保证最小堆中的所有数据都要大于最大堆中的数据 …… 【实现策略】 使用优先队列 PriorityQueue 实现最大堆和最小堆优先队列的底层实现是一个最小堆通过重写比较器的方法可以将其改为大根堆 更多内容可参考堆的实现Java分配数据的插入位置如果数据的总数目是 偶数则把新数据插入到 小根堆否则则插入到 大根堆保证堆中数据正确即小根堆中所有数据都要大于大根堆中的数据因此就要进行判断如果出现了要插入小根堆中的数据小于大根堆中的数据的情况那么则将该数据插入到大根堆并将大根堆的队首元素最大值弹出插入到小根堆中返回中点时进行判断如果总数是偶数则返回中点两数的平均值如果是奇数则返回小根堆的最小值。 …… 【注意点】 运算符的优先级要大于 运算符 因此在判断总数目是偶数时要注意加上括号((minHeap.size() maxHeap.size()) 1) 0挺麻烦的就是说但如果你不加括号就会出现下列问题 更多内容可参考Java运算符优先级 class MedianFinder {// 最小堆 PriorityQueueInteger minHeap;// 最大堆PriorityQueueInteger maxHeap;/** initialize your data structure here. */public MedianFinder() {minHeap new PriorityQueue();maxHeap new PriorityQueue((i1, i2) - Integer.compare(i2, i1));}public void addNum(int num) {// 如果总数目是偶数则将数据存到小根堆if (((minHeap.size() maxHeap.size()) 1) 0){if (maxHeap.size() 0 num maxHeap.peek()){maxHeap.offer(num);minHeap.offer(maxHeap.poll());}else minHeap.offer(num);} else{ // 否则存到大根堆if (minHeap.size() 0 minHeap.peek() num){minHeap.offer(num); maxHeap.offer(minHeap.poll()); }else maxHeap.offer(num);}}public double findMedian() {// 总数是偶数返回两数平均值if (((minHeap.size() maxHeap.size()) 1) 0){return (double)(minHeap.peek() maxHeap.peek())/2;}else{ // 奇数返回小根堆return minHeap.peek();}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj new MedianFinder();* obj.addNum(num);* double param_2 obj.findMedian();*/代码简化 【简化思路】 思路与上面差不多只不过是简化省略了一些判断过程直接将判断的过程扔给了堆如我要向大根堆插入一个数据那么我就先要插入的数据扔到小根堆中然后我把小根堆中最小的数插入大根堆反之亦然这样始终能保持小根堆存储较大一半、大根堆存储较小一半。 class MedianFinder {QueueInteger A, B;public MedianFinder() {A new PriorityQueue(); // 小顶堆保存较大的一半B new PriorityQueue((x, y) - (y - x)); // 大顶堆保存较小的一半}public void addNum(int num) {if(A.size() ! B.size()) {A.add(num);B.add(A.poll());} else {B.add(num);A.add(B.poll());}}public double findMedian() {return A.size() ! B.size() ? A.peek() : (A.peek() B.peek()) / 2.0;}
}3. 参考资料
[1] 面试题41. 数据流中的中位数优先队列 / 堆清晰图解
