你真的会写无序数组中位数的查找算法吗?PriorityQueue的妙用-创新互联

  中位数(又称中值,英语:Median),统计学中的专有名词,代表一个样本、种群或概率分布中的一个数值,其可将数值集合划分为相等的上下两部分。对于有限的数集,可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个,通常取最中间的两个数值的平均数作为中位数。
  面试时,大家是不是经常被问到,怎么求一个无序数组(长度为n)的中位数?

创新互联拥有十年成都网站建设工作经验,为各大企业提供成都做网站、网站建设服务,对于网页设计、PC网站建设(电脑版网站建设)、成都app软件开发公司、wap网站建设(手机版网站建设)、程序开发、网站优化(SEO优化)、微网站、国际域名空间等,凭借多年来在互联网的打拼,我们在互联网网站建设行业积累了很多网站制作、网站设计、网络营销经验,集策划、开发、设计、营销、管理等网站化运作于一体,具备承接各种规模类型的网站建设项目的能力。

  面试官:知道什么是中位数吗?

  我:知道啊。

  面试官:那你写个中位数的求解方法吧。

  我:这还不简单吗?(内心:这面试官怕是一个傻子额,这么简单的问题还要问)。给我几分钟时间。

  ……

  几分钟之后,我把代码给面试官看了一下,面试官一脸嫌弃的望着我。

  我的代码如下:

public double getMedian(int[] arr){
        if(arr.length == 0)
            return 0;
        Arrays.sort(arr);
        int mid = arr.length / 2;

        if(arr.length%2 == 1)
            return arr[mid];
        else
            return (double)(arr[mid-1] + arr[mid])/2;
    }

  面试官:还有其他方法吗?

  我:让我再想一下……额,好像用二叉堆也可以实现,不过也不用自己实现二叉堆了,毕竟JDK里面有一个类已经实现了二叉堆的数据结构,正好可以借来用一用。

  于是,我给出了如下的代码:

     优化后的代码:

public double getMedian(int[] arr){
        int heapSize = arr.length/2 + 1;
        PriorityQueue heap = new PriorityQueue<>(heapSize);
        for(int i=0; i

  面试官突然眼前一亮,连连称赞这个小伙子基础还不错。我感觉离入职又进了一步……

  最后,其实JDK里面已经给我们封装了很多好用的工具或者数据结构,在知道原理的情况下去合理使用才能提高开发效率,也不一定什么轮子都要自己造。

  欢迎大家关注我的微信公众号,不定期分享各类面试题。
你真的会写无序数组中位数的查找算法吗?PriorityQueue的妙用

创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。


当前题目:你真的会写无序数组中位数的查找算法吗?PriorityQueue的妙用-创新互联
标题链接:http://scyanting.com/article/ipgpi.html