题目及测试
package pid295; /* 数据流的中位数 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。 例如， [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 进阶: 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？ 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？ */ public class main { public static void main(String[] args) { MedianFinder obj = new MedianFinder(); obj.addNum(1); obj.addNum(2); double param_2 = obj.findMedian(); System.out.println(param_2); obj.addNum(1); param_2 = obj.findMedian(); System.out.println(param_2); } }解法1（成功，88ms，较慢）
内部有一个链表，代表一个有序的链表，有head和tail的值为Integer的min和max
内部有一个TreeMap<Integer, List<Node>> treeMap，Integer为数字，List<Node>为该数字对应的节点（可能有多个），新加入的在最后面
每次插入时，先插入treeMap里对应list的最后一个，然后得到对应节点的前一个，插入链表中。
然后移动mid1和mid2到应该对应的位置，结果返回mid1和mid2的中间值
速度是O(log n)
package pid295; import java.util.ArrayList; import java.util.List; import java.util.TreeMap; class MedianFinder { class Node{ int num; Node next; Node prev; public Node(int num){ this.num = num; } } Node head = new Node(Integer.MIN_VALUE); Node tail = new Node(Integer.MAX_VALUE); int size = 0; Node mid1 = head; Node mid2 = tail; int mid1Index = -1; int mid2Index = -1; TreeMap<Integer, List<Node>> treeMap = new TreeMap<>(); /** initialize your data structure here. */ public MedianFinder() { head.next = tail; tail.prev = head; } // head 1 2 tail public void addNum(int num) { Node now = new Node(num); List<Node> list = null; if(!treeMap.containsKey(num)){ list = new ArrayList<>(); }else{ list = treeMap.get(num); } list.add(now); treeMap.put(num, list); Node prev = null; if(treeMap.containsKey(num)&&(treeMap.get(num).size()!=1)){ list = treeMap.get(num); prev = list.get(list.size()-2); }else if(treeMap.lowerEntry(num)==null){ prev = head; }else{ list = treeMap.lowerEntry(num).getValue(); prev = list.get(list.size()-1); } now.next = prev.next; prev.next = now; now.next.prev = now; now.prev = prev; size ++; if(size == 1){ mid1 = now; mid2 = now; mid1Index = 0; mid2Index = 0; }else{ // 相同的，新加入的放到最后面 if(num<mid1.num){ mid1Index++; } if(num<mid2.num){ mid2Index++; } // 1 0 0 // 2 0 1 // 3 1 1 int mid1NowIndex = (size -1)/2; int mid2NowIndex = size/2; while(mid1Index != mid1NowIndex){ if(mid1Index<mid1NowIndex){ mid1Index++; mid1 = mid1.next; }else{ mid1Index--; mid1 = mid1.prev; } } while(mid2Index != mid2NowIndex){ if(mid2Index<mid2NowIndex){ mid2Index++; mid2 = mid2.next; }else{ mid2Index--; mid2 = mid2.prev; } } } } public double findMedian() { return ((double)mid1.num+(double)mid2.num)/2; } } /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); */解法2（别人的）
我们需要明确，对于此题而言，找到median就意味着，我们可以将此数据流分为两部分，即第一部分值全部小于median（or =），第二部分值全部大于median（or =）。
所以我们用maxheap存第一部分，并按照倒序存放；minheap来存第二部分，并按照顺序排放。
我们先立下一个约定，即maxheap总比minheap多一个，方便于我们之后进行查找。这样一来，初始第一个值就加入maxheap。
比较即将加入进heap的数字与两个堆堆顶的数字，若大于maxheap，则需要放进minheap中。
在后面陆续的增加中，我们只需保持两个heap size之间的关系，不断进行调节即可。
关于查找，那就只有两个地方可以找到median：如果是奇数，median肯定在maxheap的堆顶，直接输出即可；若是偶数，我们需要取出两个堆各自的堆顶元素，取其均值，再输出。
class MedianFinder { PriorityQueue<Integer> maxHeap; PriorityQueue<Integer> minHeap; /** initialize your data structure here. */ public MedianFinder() { maxHeap = new PriorityQueue<>((a,b) -> b - a); minHeap = new PriorityQueue<>((a,b) -> a - b); } public void addNum(int num) { if(maxHeap.size() == 0|| num <= maxHeap.peek()){ maxHeap.offer(num); }else{ minHeap.offer(num); } //exchange element because maxHeap must be larger than minHeap. if (maxHeap.size() > minHeap.size() + 1){ minHeap.add(maxHeap.poll()); }else if (maxHeap.size() < minHeap.size()){ maxHeap.add(minHeap.poll()); } } public double findMedian() { if(maxHeap.size() != minHeap.size()){ return maxHeap.peek(); }else{ return maxHeap.peek() / 2.0 + minHeap.peek() / 2.0; } } }
