【力扣100题】93.数据流的中位数

题目描述中位数是有序整数列表中的中间值。如果列表的大小是偶数则没有中间值中位数是两个中间值的平均值。示例 1输入 [MedianFinder, addNum, addNum, findMedian, addNum, findMedian] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0]解题思路总览思路时间复杂度空间复杂度适用场景排序数组O(n)O(n)简单直接插入排序O(n)O(n)数据流场景双堆对顶O(log n)O(n)本题最优解算法一排序数组简单版本思路直接用一个 vector 存储所有数字插入时放在正确位置保持有序。需要中位数时直接按索引访问。代码classMedianFinder{vectorintdata;public:voidaddNum(intnum){// 二分查找插入位置autoitlower_bound(data.begin(),data.end(),num);data.insert(it,num);}doublefindMedian(){intndata.size();if(n%21){returndata[n/2];}return(data[n/2-1]data[n/2])/2.0;}};复杂度分析复杂度分析时间复杂度O(n)- 插入O(n)二分 O(log n) 移动 O(n)- 找中位数O(1)空间复杂度O(n)算法二插入排序思路思路维护一个有序数组插入新数字时从后向前比较找到合适位置插入。代码classMedianFinder{vectorintdata;public:voidaddNum(intnum){if(data.empty()){data.push_back(num);}else{// 从后向前找插入位置data.push_back(num);for(intidata.size()-1;i0;i--){if(data[i]data[i-1]){swap(data[i],data[i-1]);}else{break;}}}}doublefindMedian(){intndata.size();if(n%21){returndata[n/2];}return(data[n/2-1]data[n/2])/2.0;}};复杂度分析复杂度分析时间复杂度O(n)- 插入O(n)最坏比较/交换 n 次- 找中位数O(1)空间复杂度O(n)算法三双堆对顶最优解思路维护两个堆大根堆 left存储较小的的那一半数字堆顶是较小的那个中位数小根堆 right存储较大的那一半数字堆顶是较大的那个中位数平衡规则left 的元素个数 right 的元素个数偶数个时中位数 (left.top() right.top()) / 2left 比 right 多一个元素奇数个时中位数 left.top()插入逻辑先放入 right然后从 right 取堆顶放入 left保证 left 中的都是较小的那一半如果 left 比 right 多一个元素先放入 left然后从 left 取堆顶放入 right保证平衡代码classMedianFinder{// left 是大根堆存储较小的一半数字priority_queueintleft;// right 是小根堆存储较大的一半数字priority_queueint,vectorint,greaterintright;public:MedianFinder(){}voidaddNum(intnum){// 默认先放入 right小根堆会自动排序right.push(num);// 从 right 取堆顶放入 left保证 left 的数字都 right 的数字left.push(right.top());right.pop();// 平衡如果 left 比 right 多则调整if(left.size()right.size()){right.push(left.top());left.pop();}}doublefindMedian(){if(left.size()right.size()){// 奇数个中位数在 leftreturnleft.top();}// 偶数个中位数是两个堆顶的平均值return(left.top()right.top())/2.0;}};算法流程输入序列: [1, 2, 3] 第一步addNum(1) ------------------------------------------------------------- | right: [1] | left: [] | | right.top() 1 | | | Move 1 to left -- left: [1] right: [] | | left.size() right.size(), push left.top() to right | | 最终: left: [] | right: [1] | ------------------------------------------------------------- 第二步addNum(2) ------------------------------------------------------------- | right: [2] | left: [] | | Move 2 to left -- left: [2] right: [] | | left.size() right.size(), push left.top() to right | | 最终: left: [] | right: [1, 2] | | right: [1, 2] | (小根堆top1) | ------------------------------------------------------------- 第三步findMedian() ------------------------------------------------------------- | left.size() right.size() 1 | | 中位数 (left.top() right.top()) / 2 (无 1?) | | 问题left 为空 | -------------------------------------------------------------正确的插入流程保证 left 和 right 平衡addNum(num): 1. 先放入 right小根堆 2. 从 right 取堆顶放入 left大根堆 -- 保证 left right 3. 如果 left.size() right.size()从 left 取堆顶放回 right -- 平衡 实际执行序列 [1, 2, 3] addNum(1): right.push(1) -- right[1], left[] right.top()1 - left.push(1) -- left[1], right[] left.size() right.size()从 left 取堆顶放回 right left.pop() - left[], right.push(1) -- right[1] 结果: left[], right[1] (left.size() right.size()) addNum(2): right.push(2) -- right[1,2], left[] right.top()1 - left.push(1) -- left[1], right[2] left.size() right.size()不调整 结果: left[1], right[2] (相等) addNum(3): right.push(3) -- right[2,3], left[1] right.top()2 - left.push(2) -- left[2,1], right[3] left.size() right.size()从 left 取堆顶放回 right left.pop() - left[1], right.push(2) -- right[2,3] 结果: left[1], right[2,3] findMedian(): left.size() 1, right.size() 2 不满足 left.size() right.size() 返回 (left.top() right.top()) / 2 (1 2) / 2 1.5换个输入序列 [1, 2] 验证addNum(1): right.push(1) -- right[1] right.top()1 - left.push(1) -- left[1], right[] left.size() right.size()从 left 取堆顶放回 right left.pop() -- left[], right.push(1) -- right[1] 结果: left[], right[1] addNum(2): right.push(2) -- right[1,2] right.top()1 - left.push(1) -- left[1], right[2] left.size() right.size()不调整 结果: left[1], right[2] findMedian(): left.size() right.size() 1 返回 (1 2) / 2 1.5复杂度分析复杂度分析时间复杂度O(log n)- addNum两次堆操作每次 O(log n)- findMedianO(1)空间复杂度O(n)- 两个堆最多存 n 个元素复杂度对比总结思路平均时间最坏时间空间评价排序数组O(n)O(n)O(n)简单但慢插入排序O(n)O(n)O(n)无改进双堆对顶O(log n)O(log n)O(n)最优双堆对顶的核心思想大根堆 left 小根堆 right ─────────┐ ─────────┐ │ 较小 │ │ 较大 │ │ 一半 │ │ 一半 │ │ 数字 │ │ 数字 │ │ │ │ │ │ top小 │ │ top大 │ └────┬────┘ └────┬────┘ │ left.size() right.size() │ 或 left.size() right.size() 1 │ v 中位数计算 - 奇数left.top() - 偶数(left.top() right.top()) / 2为什么这个设计正确left 是大根堆- left.top() 是 left 中的最大值即左中位数right 是小根堆- right.top() 是 right 中的最小值即右中位数每次插入都先放 right再从 right 拿最小值放 left- 保证 left 中的所有数都 right 中的所有数平衡条件- left 要么和 right 一样多要么多一个面试追问 FAQ问题回答为什么用两个堆而不是一个一个堆无法同时知道中位数的左边界和右边界left 为什么是大根堆存储较小的那一半数字堆顶是这部分的最大值即左中位数right 为什么是小根堆存储较大的那一半数字堆顶是这部分最小值即右中位数为什么先放 right 再从 right 拿保证平衡性让 left 和 right 的数据规模相近如果 left 和 right 元素个数相差很多怎么办代码中用if (left.size() right.size())检查并调整堆的大小是 n/2 吗最坏情况是 n/2但实际根据数据分布变化相关题目题目难度核心点480. 滑动窗口中位数困难滑动窗口 双堆295. 数据流的中位数困难双堆对顶703. 数据流中的第K大元素简单堆的经典应用剑指 Offer 41. 数据流中的中位数困难同本题总结项目内容核心思想双堆对顶左堆存小的一半右堆存大的一半关键技巧插入时先右后左保证左堆最大值 右堆最小值最优时间O(log n)最优空间O(n)面试加分能画图解释清楚左右堆的平衡关系