也就是编程之美那道“寻找发帖水王的题目”， 开始看这道题目的时候，首先想到就是遍历，遍历数组所有的元素，比较元素出现的次数是否大于1/2.思路很简单，直接附上源代码。
int FindMoreHalfNumber1(int* array,int n)
{
assert(array!=NULL||n<1);
for(int i=0;i<n;++i)
{
int nTimes=0;
for(int j=0;j<n;++j)
{
if(array[j]==array[i])
++nTimes;
}
if(nTimes>n/2)
return array[i];
}
}
暴力破解的结果就是时间复杂度为O(n2)，出现在编程之美上的题目，肯定不会用暴力破解的方式，一定有更快捷的方法。
既然是求每个元素出现的次数，那么使用哈希表。因为int型的范围过大，我们不能使用数组来定义哈希表。C++标准库有一个map容器。
int FindMoreHalfNumber2(int* array,int n)
{
assert(array!=NULL||n<1);
map<int,int>num_count;
for(int i=0;i<n;++i)
++num_count[array[i]];
map<int,int>::iterator it=num_count.begin();
int target=it->first;
int nTimes=it->second;
for(++it;it!=num_count.end();++it)
{
if(it->second>nTimes)
{
nTimes=it->second;
target=it->first;
}
}
return target;
}
代码本身来看，只遍历一次数组，遍历一次map容器，时间复杂度好像很低。但是实际不然，熟悉map容器的人都知道，map容器内部是按照键值进行排序，数组元素插入容器中的开销也是很大，尤其是当数组元素种类很多的时候。这样的效率也不是很理想。
书中作者给出的暴力解法是排序，因为要找的数字出现次数超过一半，排好序以后n/2处的肯定是要找的数。排序我们使用快速排序
void QuickSort(int* array,int begin,int end)
{
if(begin<end)
{
int i=begin,j=end;
int key=array[i];
while(i<j)
{
while(i<j&&array[j]>=key)
--j;
if(i<j)
array[i++]=array[j];
while(i<j&&array[i]<key)
++i;
if(i<j)
array[j--]=array[i];
}
array[i]=key;
QuickSort(array,begin,i-1);
QuickSort(array,i+1,end);
}
}
int FindMoreHalfNumber3(int* array,int n)
{
assert(array!=NULL||n<1);
QuickSort(array,0,n-1);
return array[n/2];
}
快排的时间复杂度为O(nlogn),找出这个数的时间复杂度也就是O(nlogn)
书中作者最后给出的代码是我无论如何想不出来的，思路是这样的，既然出现次数超过一半，那么如果每次删除两个不同的数字（不管是否包含我们要找的那个数），在那个超过一半的数在剩下元素中一定还超过一半，重复上述过程，降低数组总数。代码如下：
int FindMoreHalfNumber4(int* array,int n)
{
assert(array!=NULL||n<1);
inttarget=array[0];
intnTimes=1;
for(inti=1;i<n;++i)
{
if(nTimes==0){
target=array[i];
nTimes=1;
}
else if(target==array[i])
++nTimes;
else
--nTimes;
}
return target;
}
时间复杂度为O(n),空间复杂度为O(1)。这个思路太好了，非常新奇。这个思路很强的约束条件，必须超过一半，等于一半都不可以。好像是不是腾讯吧，把这道稍微变动了一下，找出出现次数大于等于一半的那个数，有些人可能会一时被问住，对呀，如果等于一半呢？之前似乎没考虑过哎，其实很简单啦。等于一半只可能出现在数组元素个数为偶数的情况下，我们只需要选择第一个元素或者最后一个元素，先判断它是不是我们想要找的，如果不是，不用考虑它，这样不就转换成超过一半的这种情况了吗？
int FindMoreHalfNumber5(int* array,int n)
{
assert(array!=NULL||n<1);
if(n%2==0)
{
int count=0;
for(int i=0;i<n-1;++i)
{
if(array[i]==array[n-1])
++count;
}
if(count>=n/2)
return array[n-1];
//当最后一个元素不是我们要找的那个元素的时候，不考虑最后一个
n=n-1;
}
int target=array[0];
int nTimes=1;
for(int i=1;i<n;++i)
{
if(nTimes==0){
target=array[i];
nTimes=1;
}
else if(target==array[i])
++nTimes;
else
--nTimes;
}
return target;
}
最后给出编程之美这道题之后的扩展问题，找出3个出现次数超过1/4的数字。思路是一样，如果出现一个和这3个数不相等，那么删除这四个数，不影响最终的结果，给出源代码。
void FindMoreForthNumbers(int* array,intn,int& target1,int& target2,int& target3)
{
assert(array!=NULL||n<4);
intnTimes1=0;
intnTimes2=0;
intnTimes3=0;
for(inti=0;i<n;++i)
{
if(nTimes1==0)
{
target1=array[i];
nTimes1=1;
}
elseif(target1==array[i])
++nTimes1;
elseif(nTimes2==0)
{
target2=array[i];
nTimes2=1;
}
elseif(target2==array[i])
++nTimes2;
elseif(nTimes3==0)
{
target3=array[i];
nTimes3=1;
}
elseif(target3==array[i])
++nTimes3;
else
{
--nTimes1;
--nTimes2;
--nTimes3;
}
}
}