问的问题是使用
struct match_score
{
char country[20];
int score;
};
其中结构与击球手的得分和他得分的国家有关。我们必须找到他的平均水平最高的国家。
我写了一个时间复杂度为 O(n^2) 的代码 谁能建议我如何将时间复杂度降低到 O(nlogn) 或 O(n)
O(n^2) 的代码
#include <stdio.h>
#include <string.h>
struct match_score
{
char country[20];
int score;
};
char *func(struct match_score *array,int len);
main()
{
struct match_score scores[]={
{"Pakistan",23},
{"India",52},
{"Pakistan",40},
{"India",22},
{"Australia",80}
};
char *max_avg=func(scores,5);
printf("%s",max_avg);
}
char *func(struct match_score *array,int len)
{
int i,j,average[20],avg,l,max=0,max_num;
char co[20];
for(i=0;i<len;i++)
{
average[i]=0;
}
for(i=0;i<len;i++)
{
avg=0;
l=0;
strcpy(co,"");
strcpy(co,array[i].country);
for(j=0;j<len;j++)
{
if(strcmp(array[j].country,co)==0)
{
l++;
avg+=array[j].score;
}
}
average[i]=avg/l;
}
for(i=0;i<len;i++)
{
if(average[i]>max)
{
max=average[i];
max_num=i;
}
}
for(i=0;i<len;i++)
{
printf("%d %d\n",i,average[i]);
}
return array[max_num].country;
}