中位数(又称中值,英语:Median),统计学中的专有名词,代表一个样本、种群或概率分布中的一个数值,其可将数值集合划分为相等的上下两部分。对于有限的数集,可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个,通常取最中间的两个数值的平均数作为中位数。
面试时,大家是不是经常被问到,怎么求一个无序数组(长度为n)的中位数?
面试官:知道什么是中位数吗?
我:知道啊。
面试官:那你写个中位数的求解方法吧。
我:这还不简单吗?(内心:这面试官怕是一个傻子额,这么简单的问题还要问)。给我几分钟时间。
……
几分钟之后,我把代码给面试官看了一下,面试官一脸嫌弃的望着我。
我的代码如下:
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<Integer> heap = new PriorityQueue<>(heapSize);
for(int i=0; i<heapSize; i++){
heap.add(arr[i]);
}
for(int i=heapSize; i<arr.length; i++){
if(heap.peek()<arr[i]){
heap.poll();
heap.add(arr[i]);
}
}
if(arr.length % 2 == 1){
return (double)heap.peek();
}
else{
return (double)(heap.poll()+heap.peek())/2.0;
}
}
面试官突然眼前一亮,连连称赞这个小伙子基础还不错。我感觉离入职又进了一步……
最后,其实JDK里面已经给我们封装了很多好用的工具或者数据结构,在知道原理的情况下去合理使用才能提高开发效率,也不一定什么轮子都要自己造。
欢迎大家关注我的微信公众号,不定期分享各类面试题。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。