尋ねられた質問は使用しています
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;
}