我的LeetCode代码仓：https://github.com/617076674/LeetCode
原题链接：https://leetcode-cn.com/problems/find-median-from-data-stream/
题目描述：
知识点：优先队列、堆
最终，我们希望得到的数据分布结果是这样的：
如果数据是偶数个，那么最大堆left和最小堆right中的元素个数相等，且left的堆顶元素小于等于right的堆顶元素，那么我们可以取这两个堆顶元素的平均值作为中位数。
如果数据是奇数个，那么最大堆left比最小堆right中的元素少一个，且left的堆顶元素小于等于right的堆顶元素，那么我们可以取right的堆顶元素作为中位数。
那么问题来了，我们怎么样往这两个堆里添加数据才能保证得到上述分布结果呢？
（1）如果left和right都是空，即添加第一个数据的情况，直接将该数据添加进right里即可。
（2）如果left为空，right不为空，此时我们需要继续分类讨论：
a：如果新数据num小于等于right的堆顶数据，我们直接将该数据添加进left里即可。
b：否则，为了保持两个堆间的数据大小关系以及数据数目的平衡关系，我们需要将right的堆顶数据弹出并添加进left里，再将新数据添加进right里。
（3）如果left和right均不为空，此时我们仍然需要分类讨论：
a：如果此时left和right的数据数目相等，我们需要保证当数据是奇数个时，right堆的元素个数比left堆的元素个数多一个：
a-1：如果新数据num小于left的堆顶数据，我们需要将left的堆顶数据弹出并添加进right里，再将新数据num添加进left里。
a-2：否则，我们直接将该数据添加进right里即可。
b：如果此时left和right的数据数目不等，根据前面的过程，此时显然有right堆的元素个数比left堆的元素个数多一个，但我们不应该将这个差距继续扩大，因此：
b-1：如果新数据num大于right的堆顶元素，将right的堆顶元素弹出并添加进left里，再将新数据num添加进right里。
b-2：否则，我们直接往left里添加新数据num即可。
时间复杂度是O(nlogn)，其中n为数据总数。空间复杂度是O(n)。
JAVA代码：
public class MedianFinder { private PriorityQueue<Integer> left; private PriorityQueue<Integer> right; /** initialize your data structure here. */ public MedianFinder() { left = new PriorityQueue<>((a, b) -> b - a); //最大堆 right = new PriorityQueue<>(); //最小堆 } public void addNum(int num) { if (left.isEmpty() && right.isEmpty()) { right.add(num); } else if (left.isEmpty() && !right.isEmpty()) { if (num <= right.peek()) { left.add(num); } else { left.add(right.poll()); right.add(num); } } else { if (left.size() == right.size()) { if (num < left.peek()) { right.add(left.poll()); left.add(num); } else { right.add(num); } } else { if (num > right.peek()) { left.add(right.poll()); right.add(num); } else { left.add(num); } } } } public double findMedian() { int size = left.size() + right.size(); if (0 == size % 2) { return (left.peek() + right.peek()) / 2.0; } else { return right.peek(); } } }LeetCode解题报告：
用一个数组保存每个数字出现的次数。
时间复杂度和空间复杂度均是O(1)。
JAVA代码：
public class MedianFinder { int[] count; int total; /** initialize your data structure here. */ public MedianFinder() { count = new int[101]; total = 0; } public void addNum(int num) { count[num]++; total++; } public double findMedian() { if (0 == total % 2) { return (findKthNumber(total / 2) + findKthNumber(total / 2 + 1)) / 2.0; } else { return findKthNumber(total / 2 + 1); } } private int findKthNumber(int k) { int index = 0; for (int i = 0; i < 101; i++) { index += count[i]; if (index >= k) { return i; } } return -1; } }和进阶一同样的思路，只不过将大于100的数除去即可，因为有99%的整数都在0到100范围内，所以中位数一定是0到100范围内的某个数，只需根据大于100的数的个数在进阶一的基础上调整即可。
时间复杂度和空间复杂度均是O(1)。
public class MedianFinder { int[] count; int total; int greaterThan100; /** initialize your data structure here. */ public MedianFinder() { count = new int[101]; total = 0; greaterThan100 = 0; } public void addNum(int num) { if (num <= 100) { count[num]++; } else { greaterThan100++; } total++; } public double findMedian() { int temp = total - greaterThan100 * 2; if (0 == temp % 2) { return (findKthNumber(greaterThan100 + temp / 2) + findKthNumber(greaterThan100 + temp / 2 + 1)) / 2.0; } else { return findKthNumber(greaterThan100 + temp / 2 + 1); } } private int findKthNumber(int k) { int index = 0; for (int i = 0; i < 101; i++) { index += count[i]; if (index >= k) { return i; } } return -1; } }
