剑指Offer-62.数据流中的中位数(C++/Java)

题目：

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

分析：

我们可以想象出一个排序数组的中位数可以将数组分成两部分，那么我们利用最大堆和最小堆来分别存储这两部分，且如果要求中位数时，可以通过直接返回堆顶元素，在O(1)的时间内求解。

要保证最大堆的所有元素小于等于最小堆的元素，在插入元素的时候通过已插入数字数目来判断：

如果插入数目是偶数，就将元素插入最大堆，然后再将最大堆中堆顶元素取出，插入最小堆中。

如果插入数目是奇数，就将元素插入最小堆，然后再将最小堆中堆顶元素取出，插入最大堆中。

这样做就可以保证最大堆的所有元素小于等于最小堆的元素。

然后如果数目是奇数时，中位数等于最小堆的堆顶元素，为偶数时，中位数等于最小堆和最大堆的堆顶元素的平均值。

以[5,2,3,4,1,6,7,0,8]为例：

插入元素	最小堆	最大堆	中位数
5	[5]	[]	5
2	[5]	[2]	3.5
3	[3,5]	[2]	3
4	[4,5]	[3,2]	3.5
1	[3,4,5]	[2,1]	3
6	[4,5,6]	[3,2,1]	3.5
7	[4,5,6,7]	[3,2,1]	4
0	[4,5,6,7]	[3,2,1,0]	3.5
8	[4,5,6,7,8]	[3,2,1,0]	4

程序：

C++

class Solution {

public:

    void Insert(int num)

    {

        if(c %  == ){

            maxHeap.push(num);

            minHeap.push(maxHeap.top());

            maxHeap.pop();

        }

        else{

            minHeap.push(num);

            maxHeap.push(minHeap.top());

            minHeap.pop();

        }

        c++;

    }

    double GetMedian()

    {

        if(c %  == ){

            return (double)(maxHeap.top() + minHeap.top()) / ;

        }

        else{

            return (double)minHeap.top();

        }

    }

private:

    priority_queue<int, vector<int>, less<int> > maxHeap;

    priority_queue<int, vector<int>, greater<int> > minHeap;

    int c = ;

};

Java

import java.util.PriorityQueue;

import java.util.Comparator;

public class Solution {

    public void Insert(Integer num) {

        if(count % 2 == 0){

            maxHeap.offer(num);

            minHeap.offer(maxHeap.poll());

        }else{

            minHeap.offer(num);

            maxHeap.offer(minHeap.poll());

        }

        count++;

    }

    public Double GetMedian() {

        if(count % 2 == 0){

            return new Double(minHeap.peek() + maxHeap.peek()) / 2;

        }else{

            return new Double(minHeap.peek());

        }

    }

    private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

    private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11, new Comparator<Integer>() {

        @Override

        public int compare(Integer o1, Integer o2) {

            return o2 - o1;

        }

    });

    private int count = 0;

}

巴特西

剑指Offer-62.数据流中的中位数(C++/Java)

题目：

分析：

程序：

最新文章

热门文章