以前看到过这个面试题，可惜真面试时忘了。不过知不知道也没区别，因为本来也不知道解法，囧。。
题目：
有一个数组存放int型整数，数字有重复，且有一数字出现的频率超过了50%，请找出这个数字。
分析：
问了下数据量，10000的长度，数字的大小也在10000之内，数据也是乱序的。= =，估计他也没想到我会这么问，随口说的。听了这个数据范围，最先想到的就是排序+扫描，和直接标记法。
当然，这肯定不是好的方法，虽然在上述范围内可以解决，其实这个题目可以转化为另一个问题：求这个数组的中位数。至于为什么，想一下就知道。反正我当时没想到。。- -。
排序解法：
首先，对数组进行排序。10000的数据量，快排没问题。然后，直接扫描排序后的数组，找出出现频率超过50%的那个数字。扫描一遍即可。
整个算法复杂度是 O（nlogn）+O（n），完全可以胜任10000的数据量。
一点点优化：
上面说了，其实就是这就是求这个数组的中位数。所以直接输出Array[n/2]即可。这样的话，复杂度就是 O（nlogn）+O（1）。这个优化能让后面的 O(n) 变成 O(1) 。
不过，因为前面的 O（nlogn） 才是大头，所以并不是那么有成效，二者的总体复杂度还是会估计成 O（nlogn）。但无论是简洁程度还是代码量上都好很多。
标记法：
其实，这个也可以认为是一种Hash，只是因为数值小于10000，直接作为下标来Hash就可以了。在Hash的时候，计数一下，超过一半的就是要找的值。这个复杂度是 O(N) 。
如果说，数值很大，那也可用个Hash啊什么的，本质上一样，复杂度也是 O(N) 。其实也可以搞个二叉树嘛，不过复杂度要大一些了，复杂度是 O(nlogn) ，类似快排的复杂度。
以上两种，是我看到这个题目时，最先想到的思路，后面的是我后来查的网上的。
快速选择算法
这个算法和快速排序差不多，复杂度上要好些，最好情况是 O(n) 。其实就是把查找第K个值放到了快排里面，优化了一下。挺不错的算法。
其主要思想就是在快速排序中得到划分结果之后，判断要求的第k个数是在划分结果的左边还是右边，然后只处理对应的那一部分，从而达到降低复杂度的效果。
假设数组为S，先选取一个数作为基准比较数（作者称为“枢纽元”，即pivot），用快排方法把数据分为两部分Sa和Sb。
- 如果k<= |Sa|（ |Sa|表示Sa的大小），则对Sa部分用同样的方法继续操作；
- 如果k= |Sa| + 1，这个pivot就是第k大值；
- 如果k> |Sa| + 1，则对Sb部分用同样的方法查找第（k- |Sa|-1）大的值;
与快排不同，快排每次都要对划分后的两部分数据都继续进行同样的快排操作，快速选择不同，只对其中一部分进行操作即可。因为只选择一边进行递归，所以复杂度是 O(n) ，比快排要好，但是两者在最坏情况下的时间复杂度均为 O(n^2) ，出现在每次划分之后左右总有一边为空的情况下。
BFPRT算法
BFPRT算法，又称为中位数的中位数算法，由5位大牛（Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan）提出，并以他们的名字命名。参考维基上的介绍Median of medians。这个，我就完全不知道了，最坏情况下 O(n) 复杂度的算法。又看到Floyd，Tarjan的名字了，orz。
算法的思想是修改快速选择算法的主元选取方法，提高算法在最坏情况下的时间复杂度。其主要步骤为：
- 首先把数组按5个数为一组进行分组，最后不足5个的忽略。对每组数进行排序（如插入排序）求取其中位数。
- 把上一步的所有中位数移到数组的前面，对这些中位数递归调用BFPRT算法求得他们的中位数。
- 将上一步得到的中位数作为划分的主元进行整个数组的划分。
- 判断第k个数在划分结果的左边、右边还是恰好是划分结果本身，前两者递归处理，后者直接返回答案。
首先看算法的主程序，代码如下。小于5个数的情况直接处理返回答案。否则每5个进行求取中位数并放到数组前面，递归调用自身求取中位数的中位数，然后用中位数作为主元进行划分。
总结：
总的来说，算法复杂度可以达到 O(n) ,如果使用快速选择算法，耍贱点就是Hash算法(略大的空间复杂度)。挫一点的话就是快排，复杂度也在 O(nlogn)，足以抗100万级别的数据量了，一般比赛的时候基本能混过去(b_d)，除非遭遇变态强的数据。最后那个神算法真不知道。
回过头看这些算法，除了Hash外，别的算法基本都和快排有着关联，真是佩服快排的发明者。
转载请注明：旅途@KryptosX » 寻找出现频率超过一半的数
