zzzrf：数字是不断进入数组的，在每次添加一个新的数进入数组的同时返回当前新数组的中位数。
说明
中位数的定义：
- 这里的中位数不等同于数学定义里的中位数。
- 中位数是排序后数组的中间值，如果有数组中有 n 个数，则中位数为 A[(n−1)/2]。
- 比如：数组 A=[1,2,3]的中位数是 2，数组 A=[1,19]的中位数是 1 。
点此在线做题
样例 1
输入: [1,2,3,4,5]
输出: [1,1,2,2,3]
样例说明：
[1] 和 [1,2] 的中位数是 1.
[1,2,3] 和 [1,2,3,4] 的中位数是 2.
[1,2,3,4,5] 的中位数是 3.
样例 2
输入: [4,5,1,3,2,6,0]
输出: [4,4,4,3,3,3,3]
样例说明：
[4], [4,5] 和 [4,5,1] 的中位数是 4.
[4,5,1,3], [4,5,1,3,2], [4,5,1,3,2,6] 和 [4,5,1,3,2,6,0] 的中位数是 3.
题解
用 maxheap 保存左半部分的数，用 minheap 保存右半部分的数。 把所有的数一左一右的加入到每个部分。左边部分最大的数就一直都是 median 。 这个过程中，可能会出现左边部分并不完全都 <= 右边部分的情况。这种情况发生的时候，交换左边最大和右边最小的数即可。
public class Solution {
/**
* @param nums: A list of integers.
* @return: the median of numbers
*/
private PriorityQueue<Integer> maxHeap, minHeap;
private int numOfElements = 0;
public int[] medianII(int[] nums) {
// write your code here
Comparator<Integer> revCmp = new Comparator<Integer>() {
@Override
public int compare(Integer left, Integer right) {
return right.compareTo(left);
}
};
int cnt = nums.length;
maxHeap = new PriorityQueue<Integer>(cnt, revCmp);
minHeap = new PriorityQueue<Integer>(cnt);
int[] ans = new int[cnt];
for (int i = 0; i < cnt; ++i) {
addNumber(nums[i]);
ans[i] = getMedian();
}
return ans;
}
void addNumber(int value) {
maxHeap.add(value);
if (numOfElements%2 == 0) {
if (minHeap.isEmpty()) {
numOfElements++;
return;
}
else if (maxHeap.peek() > minHeap.peek()) {
Integer maxHeapRoot = maxHeap.poll();
Integer minHeapRoot = minHeap.poll();
maxHeap.add(minHeapRoot);
minHeap.add(maxHeapRoot);
}
}
else {
minHeap.add(maxHeap.poll());
}
numOfElements++;
}
int getMedian() {
return maxHeap.peek();
}
}
binux：我还以为你有几亿个数据流找中位数呢。
AlohaV2：https://i.loli.net/2020/09/22/zoI9BSqLpxVgPQX.jpg
推广请发推广区吧。另外不要标题党，LC 很久前就有这题了 https://leetcode.com/problems/find-median-from-data-stream/
txx：直接上平衡树啊，求 k 大数不是标准模板题么
Google 的磁悬浮负载均衡器holinhot：https://research.google/pubs/pub44824/ 想试一试这个磁悬浮负载均衡器， 文档我看了，说得很牛逼的样子，但是我找了很久没找到在哪下载啊。 难道不是开源的，只是出来水一下让大家看吗？holinhot：https://opensource.google/projects/list/featured 在这也没找…
一个 Google Drive 搜索引擎xinyana：https://zhao.pp.ua 一个基于ElasticSearch的 Google Drive 搜索引擎,可搜索、可直接下载
Google Chrome Helper 问题fox：macbook 疯狂风扇旋转，cpu100，一看是 Google Chrome Helper 占了 99 的 cpu，沙掉就好了。 这个问题几天内发生了两次了，查了一下似乎是一个历史遗留问题。 都 2020 年了，为啥还没修复这个问题。
谷歌云(Google Cloud)免费政策改变了？只有三个月了吗？jememouse：https://cloud.google.com/free/docs/gcp-free-tier?hl=zh-cn 有没有朋友最近新建过，是否只有三个月了？Tink：是的 gqbre：握草。。 白嫖的日子一去不复返 trepwq：是…
华为手机 google play 付款问题brnznf：现在用 magic2，在谷歌商店里为 google play 账号充值，选择金额继续就闪退了。此外，应用内购买，付款的时候也闪退了。大家知道怎么回事吗？