Moving Median
这是和Moving Average一样的一个统计学常用的方法. 这个比那个average更(有用). 用一个最大堆和一个最小堆维护. 先往最小堆里放第一个元素, 然后其他元素就比一下, 如果比最小堆的顶元素小或者等于, 就放最小堆,不是就放最大堆. 然后还需要一个rebalance的方法, 如果其中一个堆比另一个堆多一个以上,就扔过去一个.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
import java.util.Collections; import java.util.PriorityQueue; /** * Created by Chenguang He ([email protected]) on 10/5/15. */ public class MovingMedian { private PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder()); private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(); public void add(Integer i) { if (minHeap.isEmpty() && maxHeap.isEmpty()) minHeap.add(i); else { if (i <= minHeap.peek()) minHeap.add(i); else maxHeap.add(i); rebalance(); } } private void rebalance(){ if (minHeap.size() < maxHeap.size()-1) { minHeap.add(maxHeap.remove()); } else if (minHeap.size() > maxHeap.size() +1){ maxHeap.add(minHeap.remove()); } } public float getMedian(){ if (minHeap.size() == 0 && maxHeap.size() == 0) return -1; else if (minHeap.size() == maxHeap.size()) return (float)(minHeap.peek()+maxHeap.peek())/(float)2; else return (minHeap.size() < maxHeap.size()) ? maxHeap.peek():minHeap.peek(); } public static void main(String[] args) { int[] t = new int[]{4,-2,1,2,-3}; MovingMedian m = new MovingMedian(); for (int tt : t) m.add(tt); System.out.println(m.getMedian()); } } |