原创

【剑指Offer】063——数据流中的中位数 (数值)

题目描述

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。

解题思路

Java解决思想

我们可以将数据排序后分为两部分,左边部分的数据总是比右边的数据小。那么,我们就可以用最大堆和最小堆来装载这些数据:

  • 最大堆装左边的数据,取出堆顶(最大的数)的时间复杂度是O(1)
  • 最小堆装右边的数据,同样,取出堆顶(最小的数)的时间复杂度是O(1)

从数据流中拿到一个数后,先按顺序插入堆中:如果左边的最大堆为空或者该数小于等于最大堆顶的数,则把它插入最大堆,否则插入最小堆。然后,我们要保证左边的最大堆的size等于右边的最小堆的size或者最大堆的size比最小堆的size大1。
要获取中位数的话,直接判断最大堆和最小堆的size,如果相等,则分别取出两个堆的堆顶除以2得到中位数,不然,就是最大堆的size要比最小堆的size大,这时直接取出最大堆的堆顶就是我们要的中位数。

最大堆:根结点的键值是所有堆结点键值中最大者,且每个结点的值都比其孩子的值大。

最小堆:根结点的键值是所有堆结点键值中最小者,且每个结点的值都比其孩子的值小。

Python解决思想

插入一个数值排一次序,取中位数时直接取中间的即可。

参考代码

Java

import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
    // 最小堆(右)
    private PriorityQueue<Integer> rHeap = new PriorityQueue<>();
    // 最大堆(左)
    private PriorityQueue<Integer> lHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
    // 保证lHeap.size()>=rHeap.size()
    public void Insert(Integer num) {
        // 先按大小插入,再调整
        if(lHeap.isEmpty() || num <= lHeap.peek())
            lHeap.offer(num);
        else
            rHeap.offer(num);

        if(lHeap.size() < rHeap.size()){
            lHeap.offer(rHeap.peek());
            rHeap.poll();
        }else if(lHeap.size() - rHeap.size() == 2){
            rHeap.offer(lHeap.peek());
            lHeap.poll();
        }
    }
    public Double GetMedian() {
        if(lHeap.size() > rHeap.size())
            return new Double(lHeap.peek());
        else
            return new Double(lHeap.peek() + rHeap.peek())/2;
    }
}

Python

需要说明的是:在牛客中网中初始化给定的def GetMedian(self, data)中无data参数(实际中我们也没有用到,我们的数据已经存在到对象中了,不需要传进来),如果不添加data程序是通不过的。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.data= []
    def Insert(self, num):
        # write code here
        self.data.append(num)
        self.data.sort()
    def GetMedian(self, data):
        # write code here
        data_len = len(self.data)
        if data_len % 2 == 0:
            # // 向下取整
            return (self.data[data_len//2] + self.data[data_len//2 - 1])/2.0
        else:
            return self.data[data_len//2]
正文到此结束
本文目录