本文介绍: 算法常用,剑指 offer 中也会出现,这个数据结构设计的十分巧妙!这个思路很是巧妙,可以自行画图理解下~
1. 题目来源
链接:295. 数据流的中位数
相关博文:
2. 题目解析
十分经典的问题了。算法常用,剑指 offer 中也会出现,这个数据结构设计的十分巧妙!
思路:
- 中位数,实际上就是将数组分成有序的两段,L、R。当 L == R 时就是两端相邻点的平均值,当 L = R +1 时,就是 L 中多出来的那个数。
- 如果需要动态维护的话,一般思路:
- 将 L 设置成大顶堆,L 中实际上存的是数组中较小的一部分数,而堆顶是这较小数的最大值,方便向 R 去移动。
- 将 R 设置成小顶堆,R 中实际上存的是数组中较大的一部分数,而堆顶是这较大数的最小值,方便向 L 去移动。
- 设定:L.size() >= R.size() + 1,我们设置 L 的元素个数至多比 R 多一个。在这个设置下,中位数就可以从两个堆顶元素求得了。
- 当 num 进入时,如果:
- L.size() == R.size(),加入后,应当变成 L.size() = R.size() + 1,那么我们希望从将 R 中最小的一个加入到 L 中,所以 num 先进入 R,然后再将 R 堆顶元素加入 L,最后将 R 堆顶元素弹出。这样子做,不需要考虑 num 与 L、R 堆顶元素的大小关系。
- L.size() != R.size(),说明 L.size() = R.size() +1,加入后,应当变成 L.size() == R.size() 才对,那么我们希望将 L 中最大的一个加入到 R 中去,所以 num 先进入 L 进行比较,然后再将 L 的堆顶元素加入 R,最后将 L 堆顶元素弹出,这样子做,也不需要考虑 num 与 L、R 堆顶元素的大小关系。
- 获取中位数时,两个情况:
- L.size() == R.size() 那么取 L、R 堆顶元素的平均值即可。
- L.size() != R.size() 基于我们之前的设定,现在应该是 L.size() == R.size() + 1,那么直接返回 L 的堆顶元素即为中位数。
这个思路很是巧妙,可以自行画图理解下~
学习一下这个代码实现,避免情况判断。但是在效率上可能较低,如果明确了 num 和 堆顶的关系,可能我们直接进行 push 一次就行了,但实际在这里一直都是 push 两次 pop 一次。
eg:
- 其实这里设定 L.size() >= R.size() +1 是很灵活的一个人为设定,同理我们设置 R.size() >= L.size()+1 也行,主要是为了维护左右两端的一个平衡而已。可以类比下 AVL 树。
- 时间复杂度:
O
(
n
l
o
g
n
)
O(nlogn)
- 空间复杂度:
O
(
n
)
O(n)
class MedianFinder {
public:
priority_queue<int, vector<int>, less<int>> L;
priority_queue<int, vector<int>, greater<int>> R;
MedianFinder() {
}
void addNum(int num) {
if (L.size() != R.size()) {
L.push(num);
R.push(L.top());
L.pop();
} else {
R.push(num);
L.push(R.top());
R.pop();
}
}
double findMedian() {
return L.size() == R.size() ? (L.top() + R.top()) / 2.0 : L.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
原文地址:https://blog.csdn.net/yl_puyu/article/details/135968453
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_65901.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。