Solution I:数组+Quick Select 添加时间复杂度O(1),查找时间复杂度O(n)
Solution II: 数组+插排 添加时间复杂度O(n),查找时间复杂度O(1)
Solution III:链表+插排 添加时间复杂度O(n),查找时间复杂度O(1)
Solution IV: 大堆小堆法 添加时间复杂度O(logN),查找时间复杂度O(1)
大堆小堆策略:
3.当已有偶数个数据时放入小堆,奇数个则放入大堆,数据总量为奇数时返回小堆堆顶,为偶数时返回大堆顶和小堆顶的平均数。
template<typename T>
class DynamicMiddleNum {
public:
void add(T num) {
int size = min.size() + max.size();
if (size & 1 == 0) {
if (max.size() > 0 && num < max[0]) {
max.push_back(num);
push_heap(max.begin(), max.end(), less<T>());
num = max[0];
pop_heap(max.begin(), max.end(), less<T>());
max.pop_back();
}
min.push_back(num);
push_heap(min.begin(), min.end(), greater<T>());
}else {
if (min.size() > 0 && num > min[0]) {
min.push_back(num);
push_heap(min.begin(), min.end(), greater<T>());
num = min[0];
pop_heap(min.begin(), min.end(), greater<T>());
min.pop_back();
}
max.push_back(num);
push_heap(max.begin(), max.end(), less<T>());
}
size++;
}
T getMidNum() {
int size = min.size() + max.size();
assert(size > 0);
if (size & 1)
return min[0];
else
return (max[0] + min[0]) / 2;
}
private:
vector<T> min;
vector<T> max;
};