数据流中的中位数

向右看齐 2021-11-04 09:44 345阅读 0赞

### 一、题目描述 ###

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

\[2,3,4\] 的中位数是 3

\[2,3\] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。  
double findMedian() - 返回目前所有元素的中位数。  
示例：

addNum(1)
    addNum(2)
    findMedian() -> 1.5
    addNum(3) 
    findMedian() -> 2

### 二、答题链接 ###

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/find-median-from-data-stream][https_leetcode-cn.com_problems_find-median-from-data-stream]

### 三、JAVA代码 ###

class MedianFinder {
    
       private PriorityQueue<Integer> min = new PriorityQueue<>();  //默认为最小堆
       private PriorityQueue<Integer> max = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer i, Integer j) {
                return j -i;
            }
        });
    
    public MedianFinder() {
        
    }
    
    public void addNum(int num) {
        int size = min.size() + max.size();
            if((size&1)==0){     //注意位运算需要用括号括起来
                //偶数：max中增加元素
                min.offer(num);
                num=min.poll();
                max.offer(num);
            }else{
                //奇数：min中增加元素
                max.offer(num);
                num=max.poll();
                min.offer(num);
            }
    }
    
    public double findMedian() {
        int size = min.size() + max.size();
        if ((size & 1) == 0)  //为偶数时返回中间两值的平均数，即min堆堆顶元素和max堆顶元素的均值
            return (min.peek() + max.peek()) / 2.0;
        return max.peek(); //为奇数时返回中间值，即max堆的堆顶元素
    }
    }
    
    /**
     * Your MedianFinder object will be instantiated and called as such:
     * MedianFinder obj = new MedianFinder();
     * obj.addNum(num);
     * double param_2 = obj.findMedian();
     */

### 四、写给自己 ###

#### （1）比较函数 ####

*  注意复习匿名内部类
 *  Comparator接口中需要重写的方法是`public int compare(T o1, T o2)`
 *  Comparable接口中需要重写的方法是`public int compareTo(T another)`

private PriorityQueue<Integer> max = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer i, Integer j) {
                return j -i;
            }
        });

**关于Comparator和Compareble的比较：**

1）Comparable 与Comparator都是java的接口，用来对自定义的实体对象进行比较；

2）Comparable 是定义在实体类**内部**的，所以实体类对象本身就有比较大小的可能。但如果想换一种比较规则，如先按年龄后按名字排序，那么就必须修改实体类Person本身；

3）Comparator是在**实体类外部实现比较器**的，所以对List排序时必须同时传入数据和比较器，如Collections.sort(list, new MyComparator());如果想换一种比较规则，则仅需要修改比较器MyComparator,而实体类Person则不需要改变；所以建议使用这种方法；

4）Comparable实现代码相对简单，Comparator实现代码相对复杂一点，但还是建议使用Comparator方法。

原文链接：[https://blog.csdn.net/wxx614817/article/details/50628197][https_blog.csdn.net_wxx614817_article_details_50628197]

#### （2）Integer与Double的转换 ####

return (min.peek()+max.peek()) / Double.valueOf(2);  //可Accept
    return (min.peek()+max.peek() ) / 2.0; //可Accept
    return (min.peek()+max.peek() ) / 2; //错误
    return Double.valueOf( (max.peek() + min.peek())/2 ); //错误

关于`Double.valueOf()`：

//参数为double类型
    public static Double valueOf(double d) {
            return new Double(d);
    }
    //参数为String类型
    public static Double valueOf(String s) throws NumberFormatException {
            return new Double(parseDouble(s));
    }

关于Integer类型数的除法：

public void test(){
            System.out.println(5/3); //输出 1，存在精度就是问题
            System.out.println((double)(5/3)); //输出 1.0，存在精度丢失问题
            System.out.println(Double.valueOf(5/3)); //输出 1.0，存在精度丢失问题
            System.out.println(5.0/3);  // 输出1.6666666666666667
        }

从上述测试来看，两个Integer类型数进行除法运算，只会保留整数，即使将结果转换为double，也只是在小数位上添加0，实际计算所得的小数部分已经丢失。

如果保留小数部分，在进行除法之前就要完成将Integer类型进行转化，例如\*1.0或者new Double(2)、亦或者Double.valueOf(2);

#### （3）float与double ####

float:单精度类型,精度是8位有效数字，取值范围是10的-38次方到10的38次方，float占用4个字节的存储空间  
double:双精度类型，精度是17位有效数字，取值范围是10的-308次方到10的308次方，double占用8个字节的存储空间

**若不声明的，默认小数都用double来表示，所以如果要用float的话，则应该在其后加上f**  
例如：float a=1.63;//会显示错误，正确的写法为float a=1.63f;  
则会提示不能将double转化成float 这成为窄型转化

注意float是8位有效数字，第7位数字将会产生四舍五入  
所以如果一个float变量 这样定义: float a=1.32344435; 则第7位将产生四舍五入(5及5以下的都将舍去)

**一般开发中建议用double 修饰小数**

原文链接：[https://blog.csdn.net/qzw5235641/article/details/84676881][https_blog.csdn.net_qzw5235641_article_details_84676881]

[https_leetcode-cn.com_problems_find-median-from-data-stream]: https://leetcode-cn.com/problems/find-median-from-data-stream
[https_blog.csdn.net_wxx614817_article_details_50628197]: https://blog.csdn.net/wxx614817/article/details/50628197
[https_blog.csdn.net_qzw5235641_article_details_84676881]: https://blog.csdn.net/qzw5235641/article/details/84676881