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