JAVA学习-练习试用Java实现“数据流的中位数”
问题：
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
解答思路：
以下是使用 Java 语言实现的解决方案：
import java.util.PriorityQueue;public class MedianFinder {// 最大堆，存储较小的一半元素private PriorityQueue<Integer> smallerHalf;// 最小堆，存储较大的一半元素private PriorityQueue<Integer> largerHalf;public MedianFinder() {smallerHalf = new PriorityQueue<>((a, b) -> b - a);largerHalf = new PriorityQueue<>();}public void addNum(int num) {// 将元素添加到较小的一半中smallerHalf.offer(num);// 将较小一半中的最大元素移动到较大的一半中largerHalf.offer(smallerHalf.poll());// 如果较小的一半元素数量小于较大的一半，则将较大一半中的最小元素移动到较小的一半中if (smallerHalf.size() < largerHalf.size()) {smallerHalf.offer(largerHalf.poll());}}public double findMedian() {// 如果较小的一半元素数量等于较大的一半，则中位数为两个堆顶元素的平均值if (smallerHalf.size() == largerHalf.size()) {return (smallerHalf.peek() + largerHalf.peek()) / 2.0;} else {// 否则，中位数为较小一半的堆顶元素return smallerHalf.peek();}}public static void main(String[] args) {MedianFinder medianFinder = new MedianFinder();medianFinder.addNum(1);medianFinder.addNum(2);System.out.println(medianFinder.findMedian()); medianFinder.addNum(3);System.out.println(medianFinder.findMedian()); }
}在上述代码中，我们使用两个优先队列（PriorityQueue）来维护数据流的中位数。一个优先队列（smallerHalf）用于存储较小的一半元素，另一个优先队列（largerHalf）用于存储较大的一半元素。
'addNum' 方法用于将新的元素添加到数据结构中。它首先将元素添加到较小的一半中，然后将较小一半中的最大元素移动到较大的一半中。如果较小的一半元素数量小于较大的一半，则将较大一半中的最小元素移动到较小的一半中，以保持两个堆的大小平衡。
'findMedian' 方法用于返回当前所有元素的中位数。如果较小的一半元素数量等于较大的一半，则中位数为两个堆顶元素的平均值。否则，中位数为较小一半的堆顶元素。
在 'main' 方法中，我们创建了一个 'MedianFinder' 对象，并使用 'addNum' 方法添加了一些元素。然后，我们使用 'findMedian' 方法获取并打印当前的中位数。
(文章为作者在学习java过程中的一些个人体会总结和借鉴，如有不当、错误的地方，请各位大佬批评指正，定当努力改正，如有侵权请联系作者删帖。)