寻找主元

  给定一个数组a，数组a大小为n，即它有n个元素。如果某个元素X在数组中出现的次数>n/2 ,那么称X为数组a的主元

  比如，数组a={1,2,3,4,5,6,78,9}，则数组a没有主元

  再如a={1,2,2,2,3}则数组a的主元为2

  易知一个数组要么没有主元，要么（只）有一个主元。

  现，给定一个数组a和它的大小，返回它的主元或者报告它无主元

  Knuth给出了一个算法，这个算法是递归的，它通过寻找候选元来寻找可能的主元。

  这里给出一种新的思路，这种思路基于：如果一个数组a有主元，那么它的主元必定是它的中位数。怎么证明呢？

  so，只要找到中位数，继而判断它到底是不是主元，即可。

  显然，主元的寻找总是可以在O(n)时间内解决。