LeetCode：295. 數據流的中位數

這個題目最快的解法應該是維護中位數，每插入一個數都能快速得到一個中位數。
根據數據范圍，我們應當實現一個$O(nlogn)$的算法。

1、超時—插入排序

使用數組存儲，維持數組有序，當插入一個元素時使用插入排序維持數組有序，這種方式無異于使用插入排序，時間復雜度不達標。

• 時間復雜度：$O(n^2)$，由于每一個數都會被插入一次，插入一次的時間為$O(n)$
• 空間復雜度：$O(n)$
  

class MedianFinder {
public:MedianFinder() {}void addNum(int num) {nums.emplace_back(num);for(int i = nums.size() - 1; i >= 1; -- i){if(nums[i] >= nums[i - 1]) break;swap(nums[i], nums[i-1]);}}double findMedian() {int mid = nums.size() / 2;if(nums.size() % 2 == 1)return 1.0 * nums[mid];return 1.0 * (nums[mid] + nums[mid - 1]) / 2;}
private:vector<int> nums;
};

2、中位數為根的BST

如果我們使用二分查找，找到新加入元素的位置，是否可行呢？答案是可行的，但是使用數組存儲并不能很快更新。

• 使用高效率的樹形二分查找，查找和插入效率很高，可以使用AVL、紅黑樹、B樹等
• 但這里要求的是能快速取得中位數，普通的樹形二分查找就不行了，不能通過下標快速找到。因此只能使用數組二分查找，但是插入效率又不高

根據上面的討論，我們發現，如果能每次插入維護的一個二叉搜索樹是一個完全二叉樹，根附近就是中位數，并且插入操作只需要$O(logn)$的時間，那就太好了。

這樣我們就可以思考，能不能實現這樣的數據結構：

• 對于任何一段區間，滿足根是中位數，且左子樹小于根，根小于右子樹的一個二叉搜索樹
  • 我們規定偶數情況下，兩個數小者作為根。如下圖：
    

如果能實現這樣的數據結構，就剛好和題目要求實現“數據結構”這一說法匹配了！
（我感覺是能實現的，但是時間問題，我就先不寫了，有興趣的同學可以自行研究）

3、優先隊列

維護兩個優先隊列，一個存儲比中位數小于的最大堆，一個存儲比中位數大的最小堆（包括等于的，即最小堆里面的元素可能會比最大堆多一個）。那么我們就將數分為了兩堆，很顯然中位數能通過某種方式從兩個優先隊列隊頭取到。

并且很顯然，維護這兩個堆也很容易，當需要插入一個數時，我們只需要比較兩個堆隊頭就可以選擇插入的堆。并且為了維持兩個堆隊頭是中位數

• 當元素數為偶數時，插入一個元素，如果插入到左邊，則最后中位數會出現在左邊，我們將其放入右邊。如果插入到右邊則直接結束
• 當元素數為奇數，插入一個元素，如果插入到左邊則結束，如果插入到右邊則右邊多一個需要放一個放到左邊。
• 不管怎么放，根據優先隊列的性質，隊頭都是最值，即根據中位數將區間分為兩段，通過優先隊列快速進行維護，左右的邊界值。

時間復雜度：$O(nlogn)$，一次插入時間復雜度$O(logn)$
空間復雜度：$O(n)$

class MedianFinder {
public:MedianFinder() {left.push(-0x3f3f3f3f);right.push(0x3f3f3f3f);}void addNum(int num) {++n;//先插入if(num >= right.top()){right.push(num);}else left.push(num);//再移動if(left.size() > right.size()){right.push(left.top());left.pop();}else{if(right.size() == left.size() + 2){left.push(right.top());right.pop();}}return;}double findMedian() {if(n & 1){//n & 1 == 1 即奇數return right.top();}return (left.top() + right.top()) / 2.0;}
private:priority_queue<int, vector<int>, less<int>> left;//左區間priority_queue<int, vector<int>, greater<int>> right;//右區間int n = 0;
};