例如,数组{1,1,2,2,4,4,4,4,5,5,6,6,6},元素1出现的次数为两次,元素2出现的次数为两次,元素4出现的次数为4次,元素5出现的次数为两次,元素6出现的次数为3次,问题就是要找出出现重复次数最多的数,所以输出应该为元素4。可以采取如下两种方法来计算数组中重复次数最多的数。
方法一:以空间换时间,可以定义一个数组int count[MAX],并将其数组元素都初始化为0,然后执行for(int i=0;i<100;i++)count[A[i]]++;操作,在count中找最大的数,即为重复次数最多的数。
程序示例如下:
#include<stdio.h>
int GetMaxNum(int* arr, int len, int& num)
{
int index=arr[0];
int i;
for(i=0; i<len; i++)
{
if(arr[i]>index)
{
index=arr[i];
num=i;
}
}
return index;
int main()
{
int array[]={1,1,2,2,4,4,4,4,5,5,6,6};
int length=sizeof(array)/sizeof(array[0]);
int i;
int num=0;
int* count=new int[GetMaxNum(array,length, num)];
for(i=0;i<length;i++)
count[i]=0;
for(i=0;i <length;i++)
count[array[i]]++;
printf("最大的数出现的次数是:%d\n",GetMaxNum(count,GetMaxNum(array,length,num),num));
printf("最大的数是:%d\n",num);
return 0;
}
程序输出结果:
最大的数出现的次数是:4
最大的数是:4
上例是一种典型的空间换时间算法。一般情况下,除非内存空间足够大,否则一般不采用这种方法。
方法二:使用map映射表,通过引入map表(map是STL的一个关联容器,它提供一对一的数据处理能力,其中第一个为关键字,每个关键字只能在map中出现一次,第二个称为该关键字的值)来记录每一个元素出现的次数,然后判断次数大小,进而找出重复次数最多的元素。
程序示例如下:
#include<iostream>
#include<map>
using namespace std;
bool findMostFrequentlnArray(int *a,int size,int&val)
{
if(size==0)
return false;
map<int,int>m;
for(int i=0;i<size;i++)
{
if(++m[a[i]]>=m[val])
vai=a[i];
}
retum true;
}
int main()
{
int a[]={1, 2, 3, 4, 4, 4, 5, 5, 5, 5, 6};
int val=0;
if(findMostFrequentInArray(a, 11, val))
cout<<val<<endl;
int b[]={1, 5, 4, 3, 4, 4, 5, 4, 5, 5, 6};
if (findMostFrequentlnArray(b, 11, val))
cout<<val<<endl;
int c[]={1, 5, 4, 3, 4, 4, 5, 4, 5, 5, 6,6, 6, 6, 6};
if (findMostFrequentlnArray(c, 15, val))
cout<<val<<endl;
return 0;
}
程序输出结果
5
5
6