Data Stream Median
Numbers keep coming, return the median of numbers at every time a new number added.
For numbers coming list: [1, 2, 3, 4, 5]
, return [1, 1, 2, 2, 3]
.
For numbers coming list: [4, 5, 1, 3, 2, 6, 0]
, return [4, 4, 4, 3, 3, 3, 3]
.
For numbers coming list: [2, 20, 100]
, return [2, 2, 20]
.
Total run time in O(nlogn).
What’s the definition of Median? – Median is the number that in the middle of a sorted array. If there are n numbers in a sorted array A, the median is A[(n - 1) / 2]
. For example, if A=[1,2,3]
, median is 2
. If A=[1,19]
, median is 1
.
Solution: 维护两个堆 左边是max heap右边是min heap。当有新的数进来时先比较两个heap的数量 永远让left和right的size一样或者left比right多1, 这样的话median永远是left.poll()。然后确定好应该加到哪个heap之后,要比较当前数和两个堆顶数的大小,来决定是直接把该数放到那个heap中还是应该把另外一个heap的root放过来然后把这个数放到另外那个堆里。
O(NlogN) time.
public int[] medianII(int[] nums) { if (nums == null || nums.length == 0) { return nums; } int initialSize = 20; int[] median = new int[nums.length]; Queue < Integer > leftHeap = new PriorityQueue < > (initialSize, new Comparator < Integer > () { public int compare(Integer a, Integer b) { return b - a; } }); Queue < Integer > rightHeap = new PriorityQueue < > (); for (int i = 0; i < nums.length; i++) { if (leftHeap.size() > rightHeap.size()) { //need to put this one to rightHeap if (nums[i] >= leftHeap.peek()) { rightHeap.offer(nums[i]); } else { rightHeap.offer(leftHeap.poll()); leftHeap.offer(nums[i]); } } else { //need to put this one to leftHeap if (leftHeap.isEmpty() && rightHeap.isEmpty()) { leftHeap.offer(nums[i]); } else { if (nums[i] <= rightHeap.peek()) { leftHeap.offer(nums[i]); } else { leftHeap.offer(rightHeap.poll()); rightHeap.offer(nums[i]); } } } median[i] = leftHeap.peek(); } return median; }