一、题目

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

点击查看原题
难度级别： 困难

二、思路

1）数组存数据+二分查找+线性插入

用一个ArrayList存储数据，保证其有序，每次插入进行二分查找位置，再插入进去
返回结果时，判断容量是否奇偶

2）大小根堆

用两个根堆，大根堆存储小值部分，小根堆存储大值部门，每次插入进行判断num该进入哪个堆，并做好两个堆数据容量的平衡
返回结果只需要判断两个根堆大小，来进行返回

三、代码

1）数组存数据+二分查找+线性插入

  1. class MedianFinder {
  2.     private List<Integer> nums;
  3.     /** initialize your data structure here. */
  4.     public MedianFinder() {
  5.         nums = new ArrayList();
  6.     }
  8.     public void addNum(int num) {
  9.         int loc = searchByBinary(num);
  10.         if (loc == nums.size()) {
  11.             nums.add(num);
  12.         } else {
  13.             nums.add(loc, num);
  14.         }
  15.     }
  17.     private int searchByBinary(int num) {
  18.         int s = 0, e = nums.size();
  19.         while (s < e) {
  20.             int mid = (s + e)/2;
  21.             if (nums.get(mid) == num) {
  22.                 return mid;
  23.             } else if (nums.get(mid) > num) {
  24.                 e = mid;
  25.             } else {
  26.                 s = mid + 1;
  27.             }
  28.         }
  29.         return s;
  30.     }
  32.     public double findMedian() {
  33.         if ((nums.size() & 1) == 1) {
  34.             return (double)nums.get(nums.size()/2);
  35.         }
  36.         return (double)((double)nums.get(nums.size()/2 - 1) + (double)nums.get(nums.size()/2 ))/2;
  37.     }
  38. }

查找和插入时间复杂度O(logn+n)，返回中位数时间复杂度O(1)，空间复杂度为O(n)

1）数组存数据+二分查找+线性插入

  1. class MedianFinder {
  2.     private PriorityQueue<Integer> minH = new PriorityQueue(); //存高部分
  3.     private PriorityQueue<Integer> maxH = new PriorityQueue<Integer>((i1, i2) -> (i2 - i1));  // 存低位
  4.     /** initialize your data structure here. */
  5.     public MedianFinder() {
  6.     }
  8.     public void addNum(int num) {
  9.         if (maxH.size() == 0) {
  10.             maxH.add(num);
  11.         } else if (maxH.peek() <= num) {
  12.             minH.add(num);
  13.             if (minH.size() > maxH.size() + 1) {
  14.                 maxH.add(minH.poll());
  15.             }
  16.         } else {
  17.             maxH.add(num);
  18.             if (maxH.size() >= minH.size() + 1) {
  19.                 minH.add(maxH.poll());
  20.             }
  21.         }
  22.     }
  24.     public double findMedian() {
  25.         if (maxH.size() == minH.size()) {
  26.             return ((double)maxH.peek() + (double)minH.peek())/2d;
  27.         }
  28.         if (maxH.size() > minH.size()) {
  29.             return (double)maxH.peek();
  30.         }
  31.         return (double)minH.peek();
  32.     }
  33. }

插入时间复杂度O(logn)，返回中位数时间复杂度O(1)，空间复杂度为O(n)