1. addNum 為第奇數筆時插入 max heap(記錄較小的那一半數字)
1.1 num <= minHeap.top()時，push num to max heap
1.2 num > minHeap.top()時，tmp = pop min heap
push tmp to max heap
push num to min heap
2. addNum 為第偶數筆時插入 min heap(記錄較大的那一半數字)
2.1 num >= maxHeap.top()時，push num to min heap
2.2 num < maxHeap.top()時，tmp = pop max heap
push tmp to min heap
push num to max heap
3. 用一個記錄結構如下:
struct{
int maxHeapPos; // 記錄 num 在 max heap 的 index 位置
int minHeapPos; // 記錄 num 在 min heap 的 index 位置
int maxHeapCount; // 記錄 num 在 max heap 的 count 數
int minHeapCount; // 記錄 num 在 min heap 的 count 數
}record[101];
3.1 push 時看是否已經存在 heap 裡(調整 count 數)，如果有的話就不用新增 node
3.2 pop 時調整 count 後的值為 0，才真的要移除該 node
3.3 新增、移除 node 時，要更新 heap 裡其它移動到的 node 的 index 位置資訊
4. findMedian:
目前筆數為奇數筆時: maxHeap.top() 就是答案
目前筆數為偶數筆時: (maxHeap.top() + minHeap.top()) / 2 就是答案
5. 少數不落在 1 ~ 100 的，不要參考第 3 大段作法就好，其它操作一樣
6 時間複雜度:
addNum: O(log n)
findMedian: O(1)
※ 引述《wawi2 (@@)》之銘言：
: 題目如同leetcode 295
: https://leetcode.com/problems/find-median-from-data-stream/
: 只需要使用有序的data structure(如set)跟一個iterator指向目前set中的medium
: 這樣就可以做到
: 不過我最近在準備面試時 看到有人遇到這題的follow ups
: 1. 如果確定資料都在1~100之間 可以怎麼改進?
: 2. 如果大部分的資料都在1~100之間 少數落在外面 又可以怎麼做?
: 請問各位有甚麼想法嗎?
※ 編輯: cutekid (111.82.116.191), 01/31/2017 09:20:34