【Hot100】LeetCode—295. 数据流的中位数

---

• 原题链接：295. 数据流的中位数

---

1- 思路

• 利用优先级队列实现一个大顶堆和一个小顶堆
• 大顶堆用来存放较小的元素，小顶堆用来存放较大的元素

① 添加元素实现

• 如果当前元素为偶数个
  • 新来元素放在小根堆中
  • 小根堆堆顶元素，放入大根堆
• 如果当前元素为奇数个
  • 新来元素放在大根堆中
  • 大根堆堆顶元素，放入小根堆

② 计算实现

• 奇数个，直接返回大根堆
• 偶数个，返回大小根堆和除以2

---

2- 实现

⭐295. 数据流的中位数——题解思路

class MedianFinder {Queue<Integer> max;Queue<Integer> min;public MedianFinder() {max = new PriorityQueue<>();min = new PriorityQueue<>((x,y) -> (y-x));}public void addNum(int num) {if(max.size()==min.size()){min.add(num);max.add(min.poll());}else{max.add(num);min.add(max.poll());}}public double findMedian() {if(max.size()==min.size()){return (max.peek()+min.peek())/2.0;}else{return max.peek()*1.0;}}
}

---