LeetCode295——Find Median from Data Stream

刺骨的言语ヽ痛彻心扉 2022-08-09 10:59 10阅读 0赞

前提是Ordered List。

但是插入即addNum操作可能是无序的。

尝试过对序列排序再返回的办法结果是超时的。想想还是天真，代码：

class MedianFinder {
    private:
    	vector<int>nums;
    public:
    
    	// Adds a number into the data structure.
    	void addNum(int num) {
    	    nums.push_back(num);
    	    sort(nums.begin(),nums.end());
    	}
    
    	// Returns the median of current data stream
    	double findMedian() {
    	    if(nums.size()%2==0)
    	    {
    	        return (nums[nums.size()/2]+nums[nums.size()/2-1])/2.0;
    	    }
    	    else
    	    {
    	        return nums[nums.size()/2];
    	    }
    	}
    };

这道题的关键在于要维护两个堆，一个大顶堆，一个小顶堆，这样保证在插入的时候就已经是有序的。

对于大顶堆，堆顶一定是堆中最大的值。

对于小顶堆，堆顶一定是堆中最小的值。

现在我们假设一个有序序列，并把这个有序列分为两半，左边一半为较小数，右边一半为较大数。

我们把较小数用大顶堆存储，较大数用小顶堆来存储。

那么大顶堆的根一定是较小数里面的最大数，小顶堆的根一定是较大数里面的最小数，也就分别是有序序列中中间的两个数。

我们在插入过程中，始终保证大小顶堆的大小差不超过·1

这样插入完成后一定有：

当大顶堆的大小=小顶堆的大小则返回 (maxHeap.top()+minHeap.top() )/2.0

当大顶堆的大小>小顶堆的大小则直接返回maxHeap.top()

否则直接返回minHeap.top()

代码：

class MedianFinder {
    private:
    	priority_queue<int,vector<int> ,less<int>> maxHeap;			// 保存较小数
    	priority_queue<int, vector<int>,greater<int>> minHeap;		// 保存较大数
    public:
    
    	// Adds a number into the data structure.
    	void addNum(int num) {
    		maxHeap.push(num);//往较小的数中添加
    		int t = maxHeap.top(); //返回较小数中的最大数
    		maxHeap.pop();
    		minHeap.push(t);//并将其添加到较大数中
    		int maxLen = maxHeap.size();
    		int minLen = minHeap.size();
    		if (minLen - maxLen > 0)
    		{
    			int t = minHeap.top();
    			maxHeap.push(t);
    			minHeap.pop();
    		}
    	}
    
    	// Returns the median of current data stream
    	double findMedian() {
    		if (maxHeap.size() > minHeap.size())
    			return maxHeap.top()*1.0;
    		else if (maxHeap.size() < minHeap.size())
    			return minHeap.top()*1.0;
    		else
    			return (minHeap.top() + maxHeap.top()) / 2.0;
    	}
    };