【剑指offer】面试题41：数据流的中位数

忘是亡心i 2022-06-11 05:10 178阅读 0赞

## 题目 ##

如何得到一个数据流中的中位数？  
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。  
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

## 思路 ##

这个题目跟一般的固定数目的数组查找中位数不一样，它是**数据流**。  
由于数据是从数据流读出来的，所以数据的数量会随着时间变化而增加。

public class Solution {
        public void insert(Integer num) {
            // TODO
        }
        public Double getMedian() {
            // TODO
        }
    }

我们要做的就是实现`insert`和`getMedian`这两个函数

这道题会有很多种思路，这里就不一一细说了，把所有解法的时间复杂度列出来：

<table> 
 <thead> 
  <tr> 
   <th>数据结构</th> 
   <th align="center">插入的时间复杂度</th> 
   <th align="center">得到中位数的时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>没有排序的数组</td> 
   <td align="center">O(1)</td> 
   <td align="center">O(n)</td> 
  </tr> 
  <tr> 
   <td>排序的数组</td> 
   <td align="center">O(n)</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td>排序的链表</td> 
   <td align="center">O(n)</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td>二叉搜索树</td> 
   <td align="center">平均O(logn)，最差O(n)</td> 
   <td align="center">平均O(logn)，最差O(n)</td> 
  </tr> 
  <tr> 
   <td>AVL树</td> 
   <td align="center">O(logn)</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td>最大堆和最小堆</td> 
   <td align="center">O(logn)</td> 
   <td align="center">O(1)</td> 
  </tr> 
 </tbody> 
</table>

**这里使用最方便的，最大堆+最小堆来做**  
思路在代码注释里↓↓↓

## 代码（解法1，优先队列） ##

#### 严重吐槽，牛客网在优先队列挂了我好多次了，好像不让用这个类！！？？有关优先队列的我后来都用红黑树做了（解法2） ####

/**
     * 题目：
     * 如何得到一个数据流中的中位数？
     * 如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
     * 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
     * 
     * 思路：
     * 用 一个最大堆  + 一个最小堆 来解决
     * 如果能够保持 最大堆里的所有元素 < 最小堆里面的所有元素
     * 如果元素总个数为奇数，最大堆元素个数=最小堆元素个数-1，则最小堆的顶部元素为中位数；
     * 如果元素总个数为偶数，最大堆元素个数=最小堆元素个数，最中位数=（最小堆的顶部元素+最大堆的顶部元素）/2
     * 
     * 解法：
     * 1.当插入第偶数个元素时（从第0个开始），将元素插入最大堆后，将最大堆顶部元素放到最小堆里
     * 2.当插入第奇数个元素时，将元素插入最小堆后，将最小堆顶部元素放到最大堆里
     * 
     * 所以当插入奇数个元素时，中位数为最小堆顶部元素；
     * 当插入偶数个元素时，中位数为（最大堆顶部元素+最小堆顶部元素）/ 2
     * 
     * @author peige
     */
    public class _41_StreamMedian_01 {
        
    
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minQ = new PriorityQueue<>();
    
        public void Insert(Integer num) {
            if(((maxQ.size() + minQ.size()) & 1) == 0) {
                maxQ.offer(num);
                minQ.offer(maxQ.remove());
            }
            else {
                minQ.offer(num);
                maxQ.offer(minQ.remove());
            }
        }
    
        public Double GetMedian() {
            if(maxQ.size() == 0 && minQ.size() == 0)
                return new Double(0.0);
            if(((maxQ.size() + minQ.size()) & 1) == 0) {
                return (double)(minQ.peek() + maxQ.peek()) / 2;
            }
            else {
                return (double)(minQ.peek());
            }
        }
    
    }

## 解法2（红黑树） ##

/**
     * 跟使用优先队列的思路一样，这里就不写了
     * 牛客网优先队列编译不过，我也是醉了。
     *  
     * @author peige
     */
    public class _41_StreamMedian_02 {
        
    
        TreeSet<Integer> maxQ = new TreeSet<>(Collections.reverseOrder());
        TreeSet<Integer> minQ = new TreeSet<>();
    
        public void Insert(Integer num) {
            if(((maxQ.size() + minQ.size()) & 1) == 0) {
                maxQ.add(num);
                minQ.add(maxQ.pollFirst());
            }
            else {
                minQ.add(num);
                maxQ.add(minQ.pollFirst());
            }
        }
    
        public Double GetMedian() {
            if(maxQ.size() == 0 && minQ.size() == 0)
                return new Double(0.0);
            if(((maxQ.size() + minQ.size()) & 1) == 0) {
                return (double)(minQ.first() + maxQ.first()) / 2;
            }
            else {
                return (double)(minQ.first());
            }
        }
    }

## 测试（这里放的红黑树的，解法1的也一样） ##

public class _41_02_Test {
        
    
        public static void main(String[] args) {
            test1();
            test2();
        }
    
        /**
         * 功能测试
         */
        private static void test1() {
            _41_StreamMedian_02 sm = new _41_StreamMedian_02();
            for(int i = 0; i < 10; ++i) {
                sm.Insert(i);
                System.out.print(sm.GetMedian() + "  ");
            }
            System.out.println();
        }
    
        /**
         * 极端测试
         * 1.没有元素，要获得中位数
         */
        private static void test2() {
            _41_StreamMedian_02 sm = new _41_StreamMedian_02();
            System.out.println(sm.GetMedian());
        }
    }