題目描述
如何得到一個數據流中的中位數？如果從數據流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值。如果從數據流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值。
算法解析： 首先我們最先想到的就是如果我們利用數組來作為數據容器，將數組排序后，十分簡便就可以獲得中位數，但這里是數據流，我們不可能在數據流中使用直接將數據放入數據容器，在取出的時候將整個數據容器排序，再取出中位數，所以如果我們將排序再度簡化，即如果有一個數組，前一半都比后一半小，那么如果數據總數是奇數的時候，我們只需要取出前一半中最大的數即可，如果是偶數我們只需要取出前一半的最大值和后一半的最小值，取其平均值即可。 這里我們選用最大堆和最小堆來實現，最大堆用于保存前一半，最小堆用于保存后一半，下面分析如何插入數據：
如果兩個堆的數據總數相同，即數據流數據總數是偶數，這里我們將數據插入最大堆。 如果插入的數字不全小于最小堆中的數，由于需要保持最小堆中的所有值大于最大堆中的所有值，所以我們將最小堆中的最小值放到最大堆，并且將插入值放入最小堆。直接放入最大堆。如果兩個堆的數據總數不同，即數據流數據總數是奇數，這里我們將數據插入最小堆。 如果插入的數字不全大于最大堆中的數，由于需要保持最小堆中的所有值大于最大堆中的所有值，所以我們將最大堆中的最大值放到最小堆，并且將插入值放入最大堆。直接放入最小堆。代碼如下：
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(); } }新聞熱點
疑難解答
