统计一个无序数组中出现次数最多的元素

问题描述：

统计一个无序数组中出现次数最多的元素。

问题分析：

可以有的一种解法是先对数组排序，所有相同的元素都会集中到一起，再进行一次遍历就能解决问题。

问题是时间的复杂度比较大，不满足一些场合下的要求。n个元素的数组，有k个不同的元素。如果频

率最高的元素的频率大于50%，满足以上条件就可以通过一次遍历解决，下面就介绍这种算法。

定义：

a[1, n]

ch = a[1]

count = 1;

for each a[i]  in a[2, n]

if (count == 0) { ch = a[i], count++;}

if (a[i] == ch) { count++;}

else { count--; }

#include<stdio.h>
/*n个字符的数组，只有一个元素出现的次数最多，找出该元素*/
char FindIt(char a[],int n)
{
  char ch;
  int times=0;
  int i;
for(i=0;i<n;i++)
{
	if(times==0)/*计数清零，从本次开始选取新的字符*/
	{
		ch=a[i];
		times=1;
	}
	else if(ch==a[i])/*找到相同的计数加1*/
			times++;
		else/*与备选的字符ch不同，计数-1.做一次抵消。只有次数最多的才会保留到最后*/
			times--;
}
return ch;
}


int main()
{
char a[]="This is a testing";/*该种情况得不到正确的答案。因为t和s出现的次数是相等的,会相互抵消掉。必须只有一个最多才成立*/
char b[]="abcdaabaaaac";/*该种情况得到正确的答案。有一个最多*/
printf("The most frequency character:%c
",FindIt(a,strlen(a)));


printf("The most frequency character:%c
",FindIt(b,strlen(b)));
return 0;
}