作者cutekid (可爱小孩子)
看板C_and_CPP
标题Re: [问题] Find the medium in the data stream
时间Mon Jan 30 17:54:28 2017
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