随机生成一些数字并传入某个方法。编写一个程序,每当收到新字符数字时,找出并记录中位数。

原创
2016/11/29 09:07
阅读数 34

类似:设计一个数据结构,包括两个函数,插入数据和获得中位数

解法:

一种解法是使用两个优先级堆:一个大根堆,存放小于中位数的值,以及一个小根堆存放大于中位数的值。这会将所有元素大致分为两半,中间的两个元素位于两个堆的堆顶。这样一来,要找到中位数就是小事一桩。

不过,“大致分为两半”又是什么意思呢?“大致”的意思是,如果有奇数个值,其中一个堆就会多一个值。经观察可知,以下两点为真。

如果maxHeap.size()>minHeap.size(),则maxHeap.top为中位数。

如果maxHeap.size()==minHeap.size(),则maxHeap.top()和minHeap.top()的平均值为中位数。

当要重新平衡这两个堆时,我们会确保maxHeap一定会多一个元素。

复制代码

//总是保证大根堆的元素大于等于小根堆的
void addNewNumber(int randomNumber)
{
//当大根堆的元素和小根堆的元素相等时
    if(maxHeap.size()==minHeap.size())
    {
        if((minHeap.peek()!=NULL&&randomNumber>minHeap.peek())//此时应该将元素插入小根堆,但是要保证大根堆的元素大于等于小根堆,所以将小根堆这最小的元素插入大根堆,然后将该元素插入小根堆
                maxHeap.offer(minHeap.poll());
                minHeap.offer(randomNumber);
            }
            else
            {
                maxHeap.offer(randomNumber);
            }
    }
    else //大根堆的元素大于小根堆,直接将元素插入小根堆
    {
        if(randomNumber<maxHeap.peek())
        {
            minHeap.offer(maxHeap.poll());
            maxHeap.offer(randomNumber);
        }
        else
        {
            minHeap.offer(randomNumber);
        }
    }
}

double getMedian()
{
    if(maxHeap.isEmpty())
    {
        return 0;
    }
    if(maxHeap.size()==minHeap.size())
    {
        return (double)(minHeap.peek()+maxHeap.peek())/2;
    }
    else
        return maxHeap.peek();
}

复制代码

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部