# 295.find-median-from-data-stream

## Statement

• Difficulty: Hard
• Tag: `设计` `双指针` `数据流` `排序` `堆（优先队列）`

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

• void addNum(int num) - 从数据流中添加一个整数到数据结构中。
• double findMedian() - 返回目前所有元素的中位数。

``````addNum(1)
findMedian() -> 1.5
findMedian() -> 2``````

1. 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
2. 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

• Link: Find Median from Data Stream
• Difficulty: Hard
• Tag: `Design` `Two Pointers` `Data Stream` `Sorting` `Heap (Priority Queue)`

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

• For example, for `arr = [2,3,4]`, the median is `3`.
• For example, for `arr = [2,3]`, the median is `(2 + 3) / 2 = 2.5`.

Implement the MedianFinder class:

• `MedianFinder()` initializes the `MedianFinder` object.
• `void addNum(int num)` adds the integer `num` from the data stream to the data structure.
• `double findMedian()` returns the median of all elements so far. Answers within `10-5` of the actual answer will be accepted.

Example 1:

``````Input
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]
Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.findMedian(); // return 2.0
``````

Constraints:

• `-105 <= num <= 105`
• There will be at least one element in the data structure before calling `findMedian`.
• At most `5 * 104` calls will be made to `addNum` and `findMedian`.

• If all integer numbers from the stream are in the range `[0, 100]`, how would you optimize your solution?
• If `99%` of all integer numbers from the stream are in the range `[0, 100]`, how would you optimize your solution?

## Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
int n;

class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {}

priority_queue<int> big;
priority_queue<int, vector<int>, greater<int>> low;

if (big.empty() && low.empty()) {
big.push(num);
return;
}

if (!big.empty()) {
if (num <= big.top())
big.push(num);
else
low.push(num);
} else {
if (num >= low.top())
low.push(num);
else
big.push(num);
}
}

double findMedian() {
while (SZ(big) > SZ(low)) {
low.push(big.top());
big.pop();
}

while (SZ(low) - 1 > SZ(big)) {
big.push(low.top());
low.pop();
}

db res = 0;

if (SZ(big) != SZ(low)) {
res = low.top();
} else {
res = (big.top() + low.top()) * 1.0 / 2;
}

return res;
}
};

/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* double param_2 = obj->findMedian();
*/

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````