Long Luo's Life Notes
·
LeetCode 第295题：从数据流中找到中位数的两个堆解决方案及后续问题
内容提要
本文讨论了LeetCode第295题“从数据流中找到中位数”的解决方案，使用两个堆来维护数据流：小根堆存储小于等于中位数的数，大根堆存储大于中位数的数。根据数据流的奇偶性动态计算中位数，并提供了在数值范围有限情况下的优化建议。
关键要点
-
使用两个堆来维护数据流：小根堆存储小于等于中位数的数，大根堆存储大于中位数的数。
-
当数据流元素总数为偶数时，中位数为两个堆顶元素的平均值；当为奇数时，中位数为小根堆的堆顶元素。
-
添加新数时，如果新数小于等于小根堆的堆顶元素，则加入小根堆；否则加入大根堆，并根据需要调整两个堆的大小。
-
时间复杂度为O(n log n)，空间复杂度为O(n)。
-
在数值范围有限的情况下，可以使用桶来优化，记录每个数的出现次数，并计算中位数。
-
如果99%的数在[0, 100]范围内，可以使用双指针和两个数组来处理范围外的数。
延伸解读
堆的使用与性能分析
使用两个堆来维护数据流的中位数是一种高效的解决方案。小根堆和大根堆的结合使得在动态数据流中快速找到中位数成为可能。尽管时间复杂度为O(n log n)，但相较于简单排序的O(n^2 log n)，性能显著提升，适合处理大规模数据流。
优化建议与应用场景
在数值范围有限的情况下，使用桶来记录每个数的出现次数可以进一步优化中位数的计算。这种方法在99%的数都在[0, 100]范围内时尤为有效，能够显著减少内存使用和计算时间，适合特定场景下的高效数据处理。
动态调整堆的策略
在添加新数时，需根据新数与小根堆顶元素的比较结果来决定将其放入哪个堆。这种动态调整策略确保了两个堆的平衡，从而保证中位数的准确性。读者在实现时需特别注意堆的大小调整，以避免数据不均衡。
延伸问答
如何使用两个堆来找到数据流的中位数？
使用小根堆存储小于等于中位数的数，大根堆存储大于中位数的数，根据数据流的奇偶性动态计算中位数。
在数据流中添加新数时需要注意什么？
如果新数小于等于小根堆的堆顶元素，则加入小根堆；否则加入大根堆，并根据需要调整两个堆的大小。
当数据流元素总数为偶数时，如何计算中位数？
中位数为两个堆顶元素的平均值。
该算法的时间复杂度和空间复杂度是多少？
时间复杂度为O(n log n)，空间复杂度为O(n)。
如何在数值范围有限的情况下优化中位数的计算？
可以使用桶来记录每个数的出现次数，并计算中位数。
如果99%的数在[0, 100]范围内，如何处理范围外的数？
可以使用双指针和两个数组来记录范围外的数，并在需要时进行暴力查找。
