题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
对于数据流，对应的就是在线算法了，一道很经典的题目就是在1亿个数中找到最大的前100个数，这是一道堆应用题，找最大的前100个数，那么我们就创建一个大小为100的最小化堆，每来一个元素就与堆顶元素比较，因为堆顶元素是目前前100大数中的最小数，前来的元素如果比该元素大，那么就把原来的堆顶替换掉。
那么对于这一道题呢？如果单纯的把所有元素放到一个数组里，每次查找中位数最快也要O(n)，综合下来是O(n^2)的复杂度。我们可以利用上面例子中的想法，用一个最大堆来维护当前前n/2小的元素，那么每次找中位数只到取出堆顶就可以了。但是，有一个问题，数据要动态增长，有可能之前被替换掉的元素随着元素的增加又跑回来了，所以我们不能单纯得向上题一样把元素丢掉，我们可以再用一个最小化堆来存前n/2大的元素。
1 #include2 using namespace std; 3 4 class Solution { 5 private: 6 vector min; //数组中的后一半元素组成一个最小化堆 7 vector max; //数组中的前一半元素组成一个最大化堆 8 public: 9 void Insert(int num) {10 if(((min.size()+max.size()) & 1) == 0) { //偶数数据的情况下，则在最小堆中插入元素11 if(max.size() > 0 && num < max[0]) {12 max.push_back(num);13 push_heap(max.begin(), max.end(), less ());14 num=max[0];15 pop_heap(max.begin(), max.end(), less ());16 max.pop_back();17 }18 min.push_back(num); //把前一半找到的最大值放到后一半中19 push_heap(min.begin(), min.end(), greater ());20 } else {21 if(min.size() > 0 && num > min[0]) { //奇数数据的情况下，则在最大堆中插入元素22 min.push_back(num);23 push_heap(min.begin(), min.end(), greater ());24 num=min[0];25 pop_heap(min.begin(), min.end(), greater ());26 min.pop_back(); 27 }28 max.push_back(num); //把后一半找到的最大值放到前一半中29 push_heap(max.begin(), max.end(), less ());30 }31 }32 33 double GetMedian() { 34 int size=min.size() + max.size();35 if(size==0) return -1;36 double median = 0;37 if((size&1) != 0) {38 median = (double) min[0];39 } else {40 median = (double) (max[0] + min[0]) / 2;41 }42 return median;43 }44 };45 46 int main() {47 Solution s;48 vector v{ 5,2,3,4,1,6,7,0,8};49 for (int i = 0; i < v.size(); ++i) {50 s.Insert(v[i]);51 cout << s.GetMedian() << endl;52 }53 return 0;54 }
也可以使用multiset来简化编程，lintcode上也有原题。
1 class Solution { 2 public: 3 /** 4 * @param nums: A list of integers. 5 * @return: The median of numbers 6 */ 7 vector medianII(vector &nums) { 8 // write your code here 9 multiset left, right;10 vector res;11 bool flag = true;12 for (int n : nums) {13 int tmp = n;14 if (flag) {15 if (!right.empty() && n > *right.begin()) {16 right.insert(n);17 tmp = *right.begin();18 right.erase(right.find(tmp));19 }20 left.insert(tmp);21 } else {22 if (!left.empty() && n < *left.rbegin()) {23 left.insert(n);24 tmp = *left.rbegin();25 left.erase(left.find(tmp));26 }27 right.insert(tmp);28 }29 flag = !flag;30 res.push_back(*left.rbegin());31 }32 return res;33 }34 }; 还有一道是求滑动窗口中的中位数，其实是基于同样的思想。只是在窗口滑动时，会有元素滑出窗口，所以在插入新的元素之前先要把滑出窗口的元素删除掉。
1 class Solution { 2 public: 3 /** 4 * @param nums: A list of integers. 5 * @return: The median of the element inside the window at each moving 6 */ 7 vector medianSlidingWindow(vector &nums, int k) { 8 // write your code here 9 vector res;10 if (k > nums.size() || k == 0) return res;11 multiset left, right;12 //init heaps by first kth elements in nums13 for (int i = 0; i < k; ++i) {14 left.insert(nums[i]);15 }16 while (left.size() > (k + 1) / 2) {17 right.insert(*left.rbegin());18 left.erase(left.find(*left.rbegin()));19 }20 res.push_back(*left.rbegin());21 //slide window22 for (int i = k; i < nums.size(); ++i) {23 //delete the leftmost element in window from heaps24 if (nums[i-k] > res.back()) right.erase(right.find(nums[i-k]));25 else left.erase(left.find(nums[i-k]));26 //insert new element into heaps27 if (!left.empty() && nums[i] <= *left.rbegin()) left.insert(nums[i]);28 else right.insert(nums[i]);29 //adjust heaps so that the left heap contains (k + 1) / 2 elements30 while (left.size() < (k + 1) / 2) {31 left.insert(*right.begin());32 right.erase(right.begin());33 }34 while (left.size() > (k + 1) / 2) {35 right.insert(*left.rbegin());36 left.erase(left.find(*left.rbegin()));37 }38 res.push_back(*left.rbegin());39 }40 return res;41 }42 };