题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
算法解析： 首先我们最先想到的就是如果我们利用数组来作为数据容器，将数组排序后，十分简便就可以获得中位数，但这里是数据流，我们不可能在数据流中使用直接将数据放入数据容器，在取出的时候将整个数据容器排序，再取出中位数，所以如果我们将排序再度简化，即如果有一个数组，前一半都比后一半小，那么如果数据总数是奇数的时候，我们只需要取出前一半中最大的数即可，如果是偶数我们只需要取出前一半的最大值和后一半的最小值，取其平均值即可。 这里我们选用最大堆和最小堆来实现，最大堆用于保存前一半，最小堆用于保存后一半，下面分析如何插入数据：
如果两个堆的数据总数相同，即数据流数据总数是偶数，这里我们将数据插入最大堆。 如果插入的数字不全小于最小堆中的数，由于需要保持最小堆中的所有值大于最大堆中的所有值，所以我们将最小堆中的最小值放到最大堆，并且将插入值放入最小堆。直接放入最大堆。如果两个堆的数据总数不同，即数据流数据总数是奇数，这里我们将数据插入最小堆。 如果插入的数字不全大于最大堆中的数，由于需要保持最小堆中的所有值大于最大堆中的所有值，所以我们将最大堆中的最大值放到最小堆，并且将插入值放入最大堆。直接放入最小堆。代码如下：
Comparator<Integer> comparator = new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } }; PRiorityQueue<Integer> maxHeap = new PriorityQueue<>(20, comparator); PriorityQueue<Integer> minHeap = new PriorityQueue<>(20); public void Insert(Integer num) { if (maxHeap.size() == minHeap.size()) { if (minHeap.peek() != null && num > minHeap.peek()) { maxHeap.offer(minHeap.poll()); minHeap.offer(num); } else { maxHeap.offer(num); } } else { if (num < maxHeap.peek()) { minHeap.offer(maxHeap.poll()); maxHeap.offer(num); } else { minHeap.offer(num); } } } public Double GetMedian() { if (maxHeap.isEmpty()) { return -1d; } if (maxHeap.size() == minHeap.size()) { return (double) (minHeap.peek() + maxHeap.peek()) / 2; } else { return (double) maxHeap.peek(); } }新闻热点
疑难解答
