栈、队列、堆--09-数据流中的中位数[困难]

2024-02-02 12:27:46

https://leetcode-cn.com/problems/find-median-from-data-stream/

https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/submissions/

题目

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

例如：

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

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

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

示例：

addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2

进阶:

如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

思路

思路1

最直观的思路是用数组来完成。时间复杂度：

若添加元素时排序，addNum复杂度为O(n)，findMedian复杂度为O(1)。
若查询中位数时排序，addNum复杂度为O(1)，findMedian复杂度为O(nlogn)。

上述最佳情况下的整体复杂度为O(n^2)。

思路2

更佳的思路：动态维护一个小顶堆和大顶堆，各存储一半的数据，保证大顶堆的堆顶比小顶堆的更小。即大顶堆存储前一半的数据流内容，小顶堆存储后一半的数据流内容。

插入数据：

情况1：

小顶堆与大顶堆元素个数相同时。如果新元素小于大顶堆，则直接插入大顶堆，否则插入小顶堆。

情况2：

大顶堆比小顶堆元素多1。

情况3：

小顶堆比大顶堆元素多1。

输出中位数：

class MedianFinder {
public:
    //大顶堆 存放前半部分数据
    priority_queue<int, vector<int>, less<int>> big_q;   
    //小顶堆 存放后半部分数据
    priority_queue<int, vector<int>, greater<int>> small_q; 
    MedianFinder() {
    }

    void addNum(int num) {
        //情况1 两者大小相同
        if (big_q.size() == small_q.size()) {
            if (big_q.size() == 0) //如果两个堆都为空
                big_q.push(num);
            else {
                if (num <= big_q.top() && big_q.top() <= small_q.top())
                    big_q.push(num);
                else if (num > big_q.top() && big_q.top() <= small_q.top())
                    small_q.push(num);
            }
        }
        //情况2 大顶堆多一个元素
        else if (big_q.size() > small_q.size()) {
            if (small_q.size() == 0) {  //处理一个堆为空的情况
                if(big_q.top() <= num)
                    small_q.push(num);
                else {
                    small_q.push(big_q.top());
                    big_q.pop();
                    big_q.push(num);
                }
            }
            else {
                if (num < big_q.top() && big_q.top() <= small_q.top()) {
                    small_q.push(big_q.top());
                    big_q.pop();
                    big_q.push(num);
                }
                else if (num >= big_q.top() && big_q.top() <= small_q.top())
                    small_q.push(num);
            }   
        }
        //情况3 小顶堆多一个元素
        else if (small_q.size() > big_q.size()) {
            if (num <= small_q.top() && big_q.top() <= small_q.top()) {
                big_q.push(num);
            }
            else if (num > small_q.top() && big_q.top() <= small_q.top()) {
                big_q.push(small_q.top());
                small_q.pop();
                small_q.push(num);
            }
        }
    }

    double findMedian() {
        //处理有的堆为空的情况
        if (small_q.empty() && big_q.empty())
            return 0.0;
        else if (small_q.size() == 0 && big_q.size() == 1)
            return big_q.top();
        else if (small_q.size() == 1 && big_q.size() == 0)
            return small_q.top();
        //处理正常情况
        else if (small_q.size() == big_q.size())
            return (small_q.top() + big_q.top()) / 2.0;
        else if (small_q.size() > big_q.size())
            return small_q.top();
        else if (small_q.size() < big_q.size())
            return big_q.top();
        else
            return 0.0;
    }
};

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

class MedianFinder {
public:
	/** initialize your data structure here. */
	//大顶堆 存放前半部分数据
	priority_queue<int, vector<int>, less<int>> big_q;   
	//小顶堆 存放后半部分数据
	priority_queue<int, vector<int>, greater<int>> small_q; 
	MedianFinder() {

	}

	void addNum(int num) {
		//情况1 两者大小相同
		if (big_q.size() == small_q.size()) {
			if (big_q.size() == 0) //如果两个堆都为空
				big_q.push(num);
			else {
				if (num <= big_q.top() && big_q.top() <= small_q.top())
					big_q.push(num);
				else if (num > big_q.top() && big_q.top() <= small_q.top())
					small_q.push(num);
			}
		}
		//情况2 大顶堆多一个元素
		else if (big_q.size() > small_q.size()) {
			if (small_q.size() == 0) {  //处理一个堆为空的情况
				if(big_q.top() <= num)
					small_q.push(num);
				else {
					small_q.push(big_q.top());
					big_q.pop();
					big_q.push(num);
				}
			}
			else {
				if (num < big_q.top() && big_q.top() <= small_q.top()) {
					small_q.push(big_q.top());
					big_q.pop();
					big_q.push(num);
				}
				else if (num >= big_q.top() && big_q.top() <= small_q.top())
					small_q.push(num);
			}	
		}
		//情况3 小顶堆多一个元素
		else if (small_q.size() > big_q.size()) {
			if (num <= small_q.top() && big_q.top() <= small_q.top()) {
				big_q.push(num);
			}
			else if (num > small_q.top() && big_q.top() <= small_q.top()) {
				big_q.push(small_q.top());
				small_q.pop();
				small_q.push(num);
			}
		}
	}

	double findMedian() {
		//处理有的堆为空的情况
		if (small_q.empty() && big_q.empty())
			return 0.0;
		else if (small_q.size() == 0 && big_q.size() == 1)
			return big_q.top();
		else if (small_q.size() == 1 && big_q.size() == 0)
			return small_q.top();
		//处理正常情况
		else if (small_q.size() == big_q.size())
			return (small_q.top() + big_q.top()) / 2.0;
		else if (small_q.size() > big_q.size())
			return small_q.top();
		else if (small_q.size() < big_q.size())
			return big_q.top();
		else
			return 0.0;
	}
};

void test01() {
	MedianFinder* obj = new MedianFinder();
	obj->addNum(6);
	obj->addNum(10);
	obj->addNum(2);
	obj->addNum(6);
	obj->addNum(5);
	obj->addNum(0);
	cout << obj->findMedian() << endl;
}

int main() {
	test01();

	system("pause");
	return 0;
}

码农公寓

相关文章