中位数（又称中值，英语：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里面已经给我们封装了很多好用的工具或者数据结构，在知道原理的情况下去合理使用才能提高开发效率，也不一定什么轮子都要自己造。

  欢迎大家关注我的微信公众号，不定期分享各类面试题。