2015年10月5日星期一

Median in a stream of integers (running integers)

Median in a stream of integers (running integers)

Given that integers are read from a data stream. Find median of elements read so for in efficient way. For simplicity assume there are no duplicates. For example, let us consider the stream 5, 15, 1, 3 …
After reading 1st element of stream - 5 -> median - 5
After reading 2nd element of stream - 5, 15 -> median - 10
After reading 3rd element of stream - 5, 15, 1 -> median - 5
After reading 4th element of stream - 5, 15, 1, 3 -> median - 4, so on...
 private void getMedian(int nums[]) {
  PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
  PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
   public int compare(Integer i1, Integer i2) {
    return i2.intValue() - i1.intValue();
   }
  });
  for (int i = 0; i < nums.length; i++) {
   int n = nums[i];
   if (maxHeap.size() == 0 || n <= maxHeap.peek()) {
    maxHeap.add(n);
   } else {
    minHeap.add(n);
   }
   if (maxHeap.size() - minHeap.size() >= 2) {
    int val = maxHeap.poll();
    minHeap.add(val);
   }
   if (minHeap.size() - maxHeap.size() >= 2) {
    maxHeap.add(minHeap.poll());
   }
   if (maxHeap.size() == minHeap.size()) {
    System.out.println((maxHeap.peek() + minHeap.peek()) / 2);
   } else if (maxHeap.size() > minHeap.size()) {
    System.out.println(maxHeap.peek());
   } else{
    System.out.println(minHeap.peek());
   }
  }
 }

没有评论:

发表评论