问题摘自《编程之美》。
问题1：一个无序数组中某一个元素A的出现次数大于总数的1/2，如何找到它？
问题2：一个无序数组中，如果有三个元素A、B、C的出现次数都大于总数的1/4，如何找到它们？
答案1：
a> 对数组排序，O(nlogn)，然后遍历一下排好序的数组，O(n)，找到最长的相同序列。（这是通用解法，然而由于A的出现大于1/2，《编程之美》中说直接取数组中位数即可）。无论如何，总体是O(nlogn)。
b> 将数组元素顺序插入一个hash表，key不存在，则val=1；当key存在，val+=1；O(n)
全部插入后，统计一下hash表中val最大的即可。缺点是需要使用hash表，空间复杂度高，在hash表中遍历原数组元素，可以保证是O(n)的。
c> 我们发现，如果每次从数组中拿出两个不同的元素，那么可能有两种情况（1，这两个元素不包含A；2，其中一个元素是A），无论哪种情况，都可以保证数组剩下的元素中，A的出现次数还是大于1/2，所以重复的拿，最后剩下的必然是A。代码如下：
int FindMajority( int* arr, int count )
{
int ret = arr[0];
int rep = 1;
for( int i = 1; i < count; ++i )
{
if( ret == arr[i] ) ++rep;
else if( --rep == 0 ) ret = arr[i+1]; // 这里放心的使用i+1不担心越界，是因为前提条件是元素出现次数大于count/2
}
return ret;
}
答案2：
与答案1的第三种方法类似，每次从数组中拿出4个互不相同的元素，这样可以保证A、B、C在这4个互不相同的元素中出现至多1次，使得剩下的元素中，依然可以保证大于1/4的比例。从而最后剩下的三种元素就是结果。代码如下：
// 由于有3个返回值，所以将它们放到参数列表里，而不是函数的返回值
int FindMajority3( int* arr, int count, int& A, int& B, int& C )
{
int repA = 0, repB = 0, repC = 0;
A = -1; // 三个初始值一定要不同，否则后续代码错误
B = -2;
C = -3;
for( int i = 0; i < count; ++i )
{
if( arr[i] == A || repA == 0 ) A = arr[i], ++repA;
else if( arr[i] == B || repB == 0 ) B = arr[i], ++repB;
else if( arr[i] == C || repC == 0 ) C = arr[i], ++repC;
else --repA, --repB, --repC;
}
}
总结：
可以发现，遇到这类问题，每次提取出一些元素，尽量保证提取出元素后，剩下的还能维持原来的比例，这样就将问题规模缩小了，另外这种方法是O(n)时间复杂度的，可以说基本上是最优的解法了。
好了，如果有人问你，一个数在无序数组中出现次数大于等于总数的2/5，找出这个数，你会做了吗？