【答案解析】如果本题对时间复杂度没有要求，可以采用很多方法。第一种方法是建立一个二维数组，一维存储数组中的数据，二维存这个数出现的次数，出现次数最多的那个数就是要找的那个数。由于某个数出现的次数超过数组长度的一半，所以二维数组的长度只需要这个数组的一半即可，但这种方法的时间复杂度和空间复杂度都比较大。
第二种方法是先对数组排序，然后取中间元素即可，因为如果某个元素的个数超过一半，那么数组排序后该元素必定占据数组的中间位置。如果出现最多的那个数是最小的，那么1～(n+1)/2都是那个数；如果出现最多的那个数是最大的，那么(n-1)/2～n都是那个数；如果不是最小也不是最大，当这个数由最小慢慢变成最大的数时，会发现中间的那个数的值是不变的，所以中间那个数就是要找的那个数。时间复杂度就是排序用的时间，即最快的排序算法的时间复杂度O(nlogn)。
但由于本题对时间复杂度有要求，以上方法显然都达不到要求，不可取，需要采取非常规方法，利用一些其他技巧来实现，于是想到了以下几种方法。
方法一：每次取出两个不同的数，剩下的数字中重复出现的数字肯定比其他数字多，将规模缩小化。如果每次删除两个不同的数(不管包括不包括最高频数)，那么在剩余的数字里，原最高频数出现的频率一样超过了50%，不断重复这个过程，最后剩下的将全是同样的数字，即最高频数。此算法避免了排序，时间复杂度只有O(n)。
程序示例如下：
#include＜stdio.h＞
int FindMostApperse(int* num,int len)
{
int candidate=0;
int count=0;
for(int i=0;i＜len;i++)
{
if(count==0)
candidate=num[i];
count=1;
}
else
{
if (candidate==num[i])
count++;
else
count--;
}
}
return candidate;
int main()
{
int arr[]={2,1,1,2,3,1,1,1};
int len=sizeof(arr)/sizeof(arr[0]);
printf("%d/n",FindMostApperse(arr, len));
return 0;
}
程序输出结果：
1
方法二：Hash法。首先创建一个hash_map，其中key为数组元素值，value为此数出现的次数。遍历一遍数组，用hash_map统计每个数出现的次数，并用两个值存储目前出现次数最多的数和对应出现的次数，此时的时间复杂度为O(n)，空间复杂度为O(n)，满足题目的要求。
方法三：使用两个变量A和B，其中变量A存储某个数组中的数，变量B用来计数。开始时将变量B初始化为0，遍历数组：
如果当前数与A不同，则需要分两种情况进行讨论：
1)如果B等于0，则令A等于当前数，令B等于1。
2)如果B大于0，则令B=B-1。
如果当前数与A相同，则令B=B+1。遍历结束时，A中存储的数就是所要找的数。这个算法的时间复杂度是O(n)，空间复杂度为O(1)。
具体代码如下：
#include＜stdio.h＞
int main()
{
int i,A,B;
int a[10]={1,2,3,1,2,1,1,6,1,1};
A=a[5];
B=0;
for(i=0;i＜10;i++)
{
if(B==0)
{
A=a[i];
B=1;
}
else if(A==a[i])
{
B++;
}
else if(A!=a[i])
{
B--;
}
}
printf("%d/n",A);
return 0;
}
程序输出结果：
1