295. 数据流的中位数
站长
· 阅读数 3
295. 数据流的中位数
😀最近新创建了个开源仓库，总结LeetCode的每日一题，目前已有C++、JavaScript语言版本，欢迎大家提供其他语言版本！ 🩲仓库地址：每日一题系列
题目描述：
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[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 范围内，你将如何优化你的算法？
解答：
C++
方法一：暴力
暴力接法：直接尾部插入，sort快速排序，取中位数
class MedianFinder {
public:
/** initialize your data structure here. */
vector<int> mem_num;
MedianFinder() {
}
void addNum(int num) {
this->mem_num.push_back(num);//插入
sort(this->mem_num.begin(),this->mem_num.end());//快排
}
double findMedian() {
int len=this->mem_num.size();
//cout<<len<<endl;
double mid_num=0;
if(len%2==0){
mid_num=(double(this->mem_num[len/2])+double(this->mem_num[len/2-1]))/2;
}else if(len%2!=0){
mid_num=double(this->mem_num[len/2]);
}
return mid_num;//中位数
}
};
优化：二分插入，取中位数
class MedianFinder {
public:
/** initialize your data structure here. */
vector<int> mem_num;
MedianFinder() {
}
void addNum(int num) {
auto addr=upper_bound(mem_num.begin(),mem_num.end(),num);
mem_num.insert(addr,num);
}
double findMedian() {
int len=this->mem_num.size();
//cout<<len<<endl;
double mid_num=0;
if(len%2==0){
mid_num=(double(this->mem_num[len/2])+double(this->mem_num[len/2-1]))/2;
}else if(len%2!=0){
mid_num=double(this->mem_num[len/2]);
}
return mid_num;
}
};
方法二：优先队列
将数据分为两个优先队列（MIN与MAX）分别记录大于中位数的数和小于等于中位数的数，优先队列中的每个元素都有优先级，而优先级高（或者低）的将会先出队，而优先级相同的则按照其在优先队列中的顺序依次出队。
优先队列往往使用堆来实现
思路：First_num优先分配给MIN优先队列，New_num大于MIN.top()分配给MAX，若MAX.size()>MIN.size()把MAX.top()给MIN使两个优先队列的队头处于中位数位置；New_num小于等于MIN.top()分配给MIN，若MAX.size()<MIN.size()+1把MIN.top()给MAX使优使两个优先队列的队头处于中位数位置；返回队头即中位数
std::priority_queue默认由大根堆实现，即最大的数在堆顶，看下图：
class MedianFinder {
public:
priority_queue<int> MIN;
priority_queue<int, vector<int>,greater<int>> MAX;
MedianFinder() {}
void addNum(int num) {
if (MIN.empty() || num <= MIN.top()) {
MIN.push(num);
if (MAX.size() + 1 < MIN.size()) {
MAX.push(MIN.top());
MIN.pop();
}
} else {
MAX.push(num);
if (MAX.size() > MIN.size()) {
MIN.push(MAX.top());
MAX.pop();
}
}
}
double findMedian() {
if (MIN.size() > MAX.size()) {
return MIN.top();
}
return (MIN.top() + MAX.top()) / 2.0;
}
};
方法三：有序集+双指针
使用multiset有序集，并维护两个指针分别指向中位数的左右两个数，下程序指针维护未看懂，可以观察实例理解；
class MedianFinder {
multiset<int> nums;//创建有序集
multiset<int>::iterator left, right;//创建中位数的双指针
public:
MedianFinder() : left(nums.end()), right(nums.end()) {}
void addNum(int num) {
int n = nums.size();//n为未插入大小
nums.insert(num);//插入数据
if (!n) {//有序集为空都指向头部
left = right = nums.begin();
} else if (n & 1) {//判断n为奇偶数，n奇数
if (num < *left) {//此时，left与right指向同一个数，此时size()为偶数，新数小于左指针指向的数,所以left——;
left--;
} else {//此时，left与right指向同一个数，此时size()为偶数，新数大于左指针指向的数,所以right++;
right++;
}
} else {//n为偶数
if (num > *left && num < *right) {//此时，left与right指向左右两个数，此时size()为奇数，新数大于左指针指向的数,且小于右指针指向的数所以left++,right--，左右指向同一处;
left++;
right--;
} else if (num >= *right) {//此时，left与right指向左右两个数，此时size()为奇数，新数大于右指针指向的数所以left++,左右指向同一处;
left++;
} else {//此时，left与right指向左右两个数，此时size()为奇数，新数小于左指针指向的数所以 right--,左右指向同一处;
right--;
left = right;
}
}
}
double findMedian() {
return (*left + *right) / 2.0;
}
};
JavaScript：
-
使用两个堆，来存储数据流
-
使用最小堆A保存较大的一半，最大堆B保存较小的一半
-
若总长度N为奇数，则A个数为
(N+1)/2，B个数为(N-1)/2 -
若总长度N为偶数，则A个数为
N/2，B个数为N/2 -
插入操作：当N为偶数，需要向A添加一个元素，先将
num插入B，再将B堆顶弹出，插入A -
插入操作：当N为奇数，需要向B添加一个元素，先将
num插入A，再将A堆顶弹出，插入B -
中位数：可以由A和B的堆顶元素得到，若N为奇数，中位数=
A的堆顶；若N为偶数，则中位数=(A的堆顶+B的堆顶)/2
const MedianFinder = function () {
// 默认最大堆
const defaultCmp = (x, y) => x > y;
// 交换元素
const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
// 堆类，默认最大堆
class Heap {
constructor(cmp = defaultCmp) {
this.container = [];
this.cmp = cmp;
}
// 插入
insert(data) {
const { container, cmp } = this;
container.push(data);
let index = this.size() - 1;
while (index) {
let parent = (index - 1) >> 1;
if (!cmp(container[index], container[parent])) {
return;
}
swap(container, index, parent);
index = parent;
}
}
// 弹出堆顶，并返回
pop() {
const { container, cmp } = this;
if (!this.size()) {
return null;
}
swap(container, 0, this.size() - 1);
const res = container.pop();
const length = this.size();
let index = 0,
exchange = index * 2 + 1;
while (exchange < length) {
// // 以最大堆的情况来说：如果有右节点，并且右节点的值大于左节点的值
let right = index * 2 + 2;
if (right < length && cmp(container[right], container[exchange])) {
exchange = right;
}
if (!cmp(container[exchange], container[index])) {
break;
}
swap(container, exchange, index);
index = exchange;
exchange = index * 2 + 1;
}
return res;
}
// 获取堆大小
size() {
return this.container.length;
}
// 获取堆顶
peek() {
if (this.size()) return this.container[0];
return null;
}
}
// 最小堆
this.A = new Heap();
// 最大堆
this.B = new Heap((x, y) => x < y);
};
MedianFinder.prototype.addNum = function (num) {
if (this.A.size() !== this.B.size()) {
// 当N为奇数，需要向B添加一个元素
// 先将num插入A，再将A堆顶弹出，插入B
this.A.insert(num);
this.B.insert(this.A.pop());
} else {
// 当N为偶数，需要向A添加一个元素
// 先将num插入B，再将B堆顶弹出，插入A
this.B.insert(num);
this.A.insert(this.B.pop());
}
};
MedianFinder.prototype.findMedian = function () {
// 若总和为偶数，返回两个堆顶的平均数
// 若总和为奇数，返回A的堆顶
return this.A.container.length === this.B.container.length
? (this.A.peek() + this.B.peek()) / 2
: this.A.peek();
};