1-题目-取中位数

一个数据流中，随时可以取得中位数
image.png

  1. import java.util.Arrays;
  2. import java.util.Comparator;
  3. import java.util.PriorityQueue;
  5. public class Code06_MadianQuick {
  7.     public static class MedianHolder {
  8.         // 大顶堆
  9.         private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new MaxHeapComparator());
  10.         // 小顶堆
  11.         private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new MinHeapComparator());
  13.         // 调整两个堆的数据，使其保持相对平衡状态（两个堆的数据的个数相差小于2）
  14.         private void modifyTwoHeapsSize() {
  15.             if (this.maxHeap.size() == this.minHeap.size() + 2) {
  16.                 this.minHeap.add(this.maxHeap.poll());
  17.             }
  18.             if (this.minHeap.size() == this.maxHeap.size() + 2) {
  19.                 this.maxHeap.add(this.minHeap.poll());
  20.             }
  21.         }
  23.         // 数据流的值应该放到哪个堆中
  24.         // 小的值放到大顶堆中
  25.         // 大的值放到小顶堆中
  26.         public void addNumber(int num) {
  27.             if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
  28.                 maxHeap.add(num);
  29.             } else {
  30.                 minHeap.add(num);
  31.             }
  32.             modifyTwoHeapsSize();
  33.         }
  35.         // 数据流的数据在都放到堆中后，便通过大顶堆和小顶堆的堆顶来计算中位数
  36.         public Integer getMedian() {
  37.             int maxHeapSize = this.maxHeap.size();
  38.             int minHeapSize = this.minHeap.size();
  39.             if (maxHeapSize + minHeapSize == 0) {
  40.                 return null;
  41.             }
  42.             Integer maxHeapHead = this.maxHeap.peek();
  43.             Integer minHeapHead = this.minHeap.peek();
  44.             if (((maxHeapSize + minHeapSize) & 1) == 0) {
  45.                 return (maxHeapHead + minHeapHead) / 2;
  46.             }
  47.             return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;
  48.         }
  50.     }
  52.     // 大顶堆比较器
  53.     public static class MaxHeapComparator implements Comparator<Integer> {
  54.         @Override
  55.         public int compare(Integer o1, Integer o2) {
  56.             if (o2 > o1) {
  57.                 return 1;
  58.             } else {
  59.                 return -1;
  60.             }
  61.         }
  62.     }
  64.     // 小顶堆比较器
  65.     public static class MinHeapComparator implements Comparator<Integer> {
  66.         @Override
  67.         public int compare(Integer o1, Integer o2) {
  68.             if (o2 < o1) {
  69.                 return 1;
  70.             } else {
  71.                 return -1;
  72.             }
  73.         }
  74.     }
  76.     // for test 生产随机数组
  77.     public static int[] getRandomArray(int maxLen, int maxValue) {
  78.         int[] res = new int[(int) (Math.random() * maxLen) + 1];
  79.         for (int i = 0; i != res.length; i++) {
  80.             res[i] = (int) (Math.random() * maxValue);
  81.         }
  82.         return res;
  83.     }
  85.     // for test, this method is ineffective but absolutely right  通过排序计算中位数，用于最后的判断
  86.     public static int getMedianOfArray(int[] arr) {
  87.         int[] newArr = Arrays.copyOf(arr, arr.length);
  88.         Arrays.sort(newArr);
  89.         int mid = (newArr.length - 1) / 2;
  90.         if ((newArr.length & 1) == 0) {
  91.             return (newArr[mid] + newArr[mid + 1]) / 2;
  92.         } else {
  93.             return newArr[mid];
  94.         }
  95.     }
  97.     public static void printArray(int[] arr) {
  98.         for (int i = 0; i != arr.length; i++) {
  99.             System.out.print(arr[i] + " ");
  100.         }
  101.         System.out.println();
  102.     }
  104.     public static void main(String[] args) {
  105.         boolean err = false;
  106.         int testTimes = 200000;
  107.         for (int i = 0; i != testTimes; i++) {
  108.             int len = 30;
  109.             int maxValue = 1000;
  110.             int[] arr = getRandomArray(len, maxValue);
  111.             MedianHolder medianHold = new MedianHolder();
  112.             for (int j = 0; j != arr.length; j++) {
  113.                 medianHold.addNumber(arr[j]);
  114.             }
  115.             if (medianHold.getMedian() != getMedianOfArray(arr)) {
  116.                 err = true;
  117.                 printArray(arr);
  118.                 break;
  119.             }
  120.         }
  121.         System.out.println(err ? "Oops..what a fuck!" : "today is a beautiful day^_^");
  123.     }
  125. }