LeetCode295数据流的中位数

思路：

• 查询流的中位数，不可以每次都在查询时排序，因为流是一直变化的，每次都要排序性能很低
• 可以使用两个堆，一个大顶堆来存储较小的数，一个小顶堆来存储较大的数
• 大顶堆 小顶堆
• 1 2 3 -- 7 8 9
• 大顶堆的最大值和小顶堆的最小值在一起，两个堆数量相等时 -> 中位数就是两堆堆顶的中位数，数量不相等时，中位数就是数量较多的堆的堆顶

如何确保两堆元素平衡

• 两边元素数相同时，向左边添加一个元素
• 元素数不相同时，向右边添加一个元素
• 在添加元素时，不可以随意加入元素，会造成两堆的大小没有保持一堆大，一堆小
• 左边添加一个元素后，为维持左堆的较小性，将左边堆顶->最大数移动到右堆
• 右边添加一个元素后，为维持右堆的较大性，将右边堆堆顶->最小数移到左堆

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 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

class MedianFinder {     PriorityQueue bigHeap; // 大顶堆记录较小值     PriorityQueue smallHeap;// 小顶堆记录较大值           public MedianFinder() {              Comparator comparator=new Comparator() {         @Override         public int compare(Integer o1, Integer o2) {             return o2-o1;         }     };          bigHeap=new PriorityQueue<>(comparator);          smallHeap=new PriorityQueue();               }           // 1      // 2 3 4 5 6      public void addNum(int num) {         // 两边个数一样时，左边添加一个元素         // 两边个数不一样时，右边添加一个元素                  // 左边添加元素时，将右边顶部元素加入         // 右边添加元素时，将左边顶部元素加入         int leftSize=bigHeap.size();         int rightSize=smallHeap.size();         if (leftSize==rightSize) {              bigHeap.offer(num);              smallHeap.offer(bigHeap.poll());                      }else {              smallHeap.offer(num);              bigHeap.offer(smallHeap.poll());         }      }          public double findMedian() {         if (bigHeap.size()==smallHeap.size()) {             return (bigHeap.peek()+smallHeap.peek())/2.0;         }else if(bigHeap.size()

输入: [3,2,1,5,6,4], k = 2 输出: 5

输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4

class Solution {     public int findKthLargest(int[] nums, int k) {     PriorityQueue heap=new PriorityQueue();// 默认小顶堆       for (int i = 0; i heap.peek()) {             heap.poll();             heap.offer(nums[i]);         }     }     return heap.peek();      } }

class KthLargest {      PriorityQueue heap ;      int size;     public KthLargest(int k, int[] nums) {         this.size = k;         heap = new PriorityQueue(k);         for(int i: nums) {             add(i);         }     }          public int add(int val) {         if(heap.size() < size) {             heap.offer(val);         }         else if(heap.peek() < val) {             heap.poll();             heap.offer(val);         }         return heap.peek();     } }