题目描述设计一个数据结构支持两个操作addNum(num)向数据流中加入一个整数 findMedian()返回当前所有整数的中位数中位数的定义是如果元素个数是奇数中位数是排序后最中间的数。如果元素个数是偶数中位数是排序后中间两个数的平均值。例如[2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 3) / 2 2.5这道题的难点在于数据是不断加入的不能每次findMedian()都重新排序。核心思路用两个堆把所有数分成左右两半l大顶堆保存较小的一半 r小顶堆保存较大的一半其中l.peek() 左半部分最大值 r.peek() 右半部分最小值这样中位数就只和两个堆顶有关如果总数是奇数中位数 l.peek() 如果总数是偶数中位数 (l.peek() r.peek()) / 2.0为什么这样分如果把所有数字排好序中位数只会出现在中间位置。所以不需要维护完整有序数组只需要维护较小的一半 | 较大的一半左边最大的数和右边最小的数正好就是中间附近的两个数。大顶堆适合快速拿到左半部分最大值小顶堆适合快速拿到右半部分最小值。关键不变量整个过程中要始终维护两个条件1. l 中的数整体 r 中的数 2. l.size() r.size()或者 l.size() r.size() 1也就是说l要么和r一样多要么只比r多一个。为什么让l多一个因为这样元素个数为奇数时可以直接返回l.peek()不用再判断中位数在哪个堆里。addNum 的过程代码中有两个分支。情况一两个堆大小相同if (l.size() r.size()) { r.offer(num); l.offer(r.poll()); }此时加入新元素后应该让l比r多一个。操作过程是1. 先把 num 放进 r 2. 再把 r 中最小的数移动到 l这样可以保证移动到l的数仍然属于较小的一半。情况二l 比 r 多一个else { l.offer(num); r.offer(l.poll()); }此时加入新元素后应该让两个堆重新变成一样大。操作过程是1. 先把 num 放进 l 2. 再把 l 中最大的数移动到 r这样可以保证移动到r的数属于较大的一半。手动模拟以依次加入1, 2, 3, 4, 5为例。这里展示的是逻辑顺序不代表 JavaPriorityQueue的真实内部数组顺序。初始l [] r []addNum(1)两个堆大小相同先放入r再把r的最小值移动到ll [1] r []当前中位数1addNum(2)l比r多一个先放入l再把l的最大值移动到rl [1] r [2]当前中位数(1 2) / 2.0 1.5addNum(3)两个堆大小相同先 r.offer(3)r [2,3] 再 l.offer(r.poll())把 2 放入 l结果l [2,1] r [3]当前中位数2addNum(4)l比r多一个先 l.offer(4)l [4,1,2] 再 r.offer(l.poll())把 4 放入 r结果l [2,1] r [3,4]当前中位数(2 3) / 2.0 2.5addNum(5)两个堆大小相同先 r.offer(5)r [3,4,5] 再 l.offer(r.poll())把 3 放入 l结果l [3,1,2] r [4,5]当前中位数3所以中位数依次是1, 1.5, 2, 2.5, 3Java 代码class MedianFinder { PriorityQueueInteger l; PriorityQueueInteger r; public MedianFinder() { l new PriorityQueue((a, b) - b - a); r new PriorityQueue(); } public void addNum(int num) { if (l.size() r.size()) { r.offer(num); l.offer(r.poll()); } else { l.offer(num); r.offer(l.poll()); } } public double findMedian() { if (l.size() r.size()) return l.peek(); return (l.peek() r.peek()) / 2.0; } }PriorityQueue 操作区分这题里最重要的是理解peek()和poll()peek()查看堆顶元素不删除 poll()取出堆顶元素并删除 offer()加入一个元素默认的PriorityQueue是小顶堆r new PriorityQueue();所以r.peek() 是 r 中的最小值如果传入比较器l new PriorityQueue((a, b) - b - a);就可以让l变成大顶堆l.peek() 是 l 中的最大值易错点PriorityQueue的队头不是最早加入的元素而是优先级最高的元素。默认PriorityQueue是小顶堆不是大顶堆。peek()只是查看堆顶poll()才会删除堆顶。只维护数量平衡还不够还要保证l.peek() r.peek()。偶数个数时要写/ 2.0否则容易写成整数除法。当前写法让l始终不少于r所以奇数时返回的是l.peek()。复杂度分析每次加入一个数时会进行堆的插入和删除addNumO(log n)查找中位数只需要看堆顶findMedianO(1)两个堆一共保存所有元素空间复杂度O(n)总结这道题的核心不是排序而是维护中位数两边的边界。用大顶堆l保存较小的一半用小顶堆r保存较大的一半。只要维护好两个不变量l 中的数整体 r 中的数 l.size() r.size() 或 l.size() r.size() 1中位数就可以通过堆顶快速得到。下次重写前可以先问自己两个堆分别保存哪一半l.peek()和r.peek()分别代表什么为什么加入元素时要先放进一个堆再把堆顶移动到另一个堆奇数个元素时为什么可以直接返回l.peek()