Long Luo's Life Notes
·
LeetCode 295. 从数据流中找到中位数：使用两个堆的解决方案及后续问题
内容提要
本文讨论了LeetCode第295题“从数据流中找到中位数”的解决方案，使用两个堆来维护数据流：小根堆存储小于等于中位数的数，大根堆存储大于中位数的数。根据数据总数的奇偶性动态计算中位数，时间复杂度为O(n log n)，空间复杂度为O(n)。还探讨了在特定范围内优化解决方案的方法。
关键要点
-
使用两个堆来维护数据流：小根堆存储小于等于中位数的数，大根堆存储大于中位数的数。
-
当数据总数为偶数时，中位数为两个堆顶元素的平均值；当数据总数为奇数时，中位数为小根堆的堆顶元素。
-
添加新数字时，根据其与小根堆最大值的比较决定将其添加到哪个堆，并可能需要调整堆的平衡。
-
时间复杂度为O(n log n)，空间复杂度为O(n)。
-
在特定范围内优化解决方案的方法包括使用桶来存储数字出现次数，并在查找中位数时进行扫描。
延伸解读
堆的使用与中位数计算
使用两个堆来维护数据流的中位数是一种高效的解决方案。小根堆和大根堆的结合使得在动态数据流中快速找到中位数成为可能。特别是在数据量较大时，这种方法的时间复杂度为O(n log n)，相较于简单排序的O(n^2 log n)显著提高了效率。
优化方案的适用场景
文章提到的优化方案适用于特定范围内的数据流，例如当所有整数都在[0, 100]范围内时，可以使用桶来存储数字出现次数。这种方法在数据分布较为集中时能够显著提高查找中位数的效率，值得在实际应用中考虑。
动态调整堆的平衡
在添加新数字时，如何动态调整两个堆的平衡是关键。根据新数字与小根堆最大值的比较，决定将其添加到哪个堆，并可能需要将堆顶元素移到另一个堆。这一过程确保了中位数的准确性，读者在实现时需特别注意这一逻辑。
延伸问答
如何使用两个堆找到数据流的中位数？
使用小根堆存储小于等于中位数的数，大根堆存储大于中位数的数，根据数据总数的奇偶性动态计算中位数。
在数据流中添加新数字时需要注意什么？
根据新数字与小根堆最大值的比较，决定将其添加到哪个堆，并可能需要调整堆的平衡。
中位数的计算方式是什么？
当数据总数为偶数时，中位数为两个堆顶元素的平均值；当数据总数为奇数时，中位数为小根堆的堆顶元素。
该算法的时间和空间复杂度是多少？
时间复杂度为O(n log n)，空间复杂度为O(n)。
如何在特定范围内优化中位数的计算？
可以使用桶来存储数字出现次数，并在查找中位数时进行扫描。
如果99%的数字在[0, 100]范围内，如何优化解决方案？
仍然可以使用桶存储数据，并使用双指针维护中位数，超出范围的数字用两个数组记录。
