AlgoPressAppearance
41-数据流中的中位数
题目描述
https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4]的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。 示例 1：
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]
限制：
- 最多会对addNum、findMedian 进行50000次调用。
- 注意：本题与主站 295 题相同：https://leetcode.cn/problems/find-median-from-data-stream/
思路
设计一个动态数组 List，在插入时保证插入后的序列仍然是有效的。 插入时为了提高效率，可以使用二分法找出索引 返回时根据个数和定义返回中位数
实现代码
csharp
public class MedianFinder {
private List<int> nums;
private int curIndex;
/** initialize your data structure here. */
public MedianFinder() {
nums = new List<int>();
}
private int findIndex(int val){
//二分查找插入位置
int left = 0;
int right = nums.Count - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(val > nums[mid]){
left = mid + 1;
}
else{
right = mid - 1;
}
}
return left;
}
public void AddNum(int num) {
if(nums.Count == 0){
nums.Add(num);
curIndex = 0;
}
else{
//找寻插入位置
curIndex = findIndex(num);
if(curIndex == nums.Count){
nums.Add(num);
}
else{
nums.Insert(curIndex,num);
}
}
}
public double FindMedian() {
if(nums.Count % 2 == 1){
return (double)nums[nums.Count/2];
}
else{
if(nums.Count == 0){
return 0;
}
else{
return (double)(nums[nums.Count / 2 - 1] + nums[nums.Count / 2]) / 2;
}
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.AddNum(num);
* double param_2 = obj.FindMedian();
*/
实现代码2： 两个优先队列
一个大根堆，一个小根堆，大根堆的数据都大于小根堆 我们维护大跟堆可以比小根堆，最多多一个
插入时，先插入小根堆，然后从小根堆中取出最大的值放入大根堆 如果测试大根堆的个数大于小根堆两个，那么从大根堆中取出最小的一个，放入小根堆
最后取中位数，如果大根堆多一个，直接返回 大根堆的min 如果两边相等，则取 大根堆的min 和小根堆的max，合并除以 2
总结步骤： 插入小 -> 小到大 -> 大到小(有需要)
注意：C# 默认没有优先队列，所以没有直接可以用优先队列来做的大根堆和小根堆 可以使用 SortedSet 模拟，注意 SortedSet 不能插入重复数据，所以要再加入一个索引，构造一个对象插入，实现 CompareTo 接口。
csharp
public class MedianFinder {
class MyNum:IComparable<MyNum>
{
public int num;
public int idx;
public MyNum(int n,int i)
{
num=n;
idx=i;
}
public int CompareTo(MyNum other)
{
var cn=num.CompareTo(other.num);
if(cn==0) return idx.CompareTo(other.idx);
return cn;
}
}
SortedSet<MyNum> small,large;
int i;
/** initialize your data structure here. */
public MedianFinder() {
small = new SortedSet<MyNum>();
large = new SortedSet<MyNum>();
i=0;
}
public void AddNum(int num) {
small.Add(new MyNum(num,i++));
large.Add(small.Max);
small.Remove(small.Max);
if(small.Count<large.Count-1)
{
small.Add(large.Min);
large.Remove(large.Min);
}
}
public double FindMedian() {
if(large.Count>small.Count) return large.Min.num/1.0;
else return large.Min.num/2.0+small.Max.num/2.0;
}
}
实现代码3： 使用 SortedList 代替优先队列【不能实现】
因为 SortedList 不能重复添加相同的key
csharp
public class MedianFinder {
private SortedList list;
public MedianFinder() {
list = new SortedList();
}
public void AddNum(int num) {
list.Add(num,num);
}
public double FindMedian() {
if(list.Count == 0){
return 0;
}
if(list.Count % 2 == 1){
return ((int)list.GetByIndex(list.Count / 2)) * 1.0;
}
else{
return ((int)list.GetByIndex(list.Count / 2) + (int)list.GetByIndex(list.Count / 2 - 1))/2.0;
}
}
}