Question

如何使用分治法求众数

在一个数组里求出现次数最多的数为众数
请用分治法求众数
要求有具体代码

Answer 1

#include<stdio.h>

int largest = 0; //the quantity
int element; //number
int a[10];
int med;

int median(int p,int r)
{
int s = r - p + 1;
if(s%2==0)
return a[s/2-1];
else
return a[s/2];
}

void split(int p,int r,int *p1,int *r1)
{
int i;
for(i=p;i<r;i++)
{
if(a[i]==med)
{
*p1 = i;
break;
}
}
for(i=*p1+1;i<r;i++)
{
if(a[i]!=med)
{
*r1 = i;
break;
}
}
}

void mode(int p,int r)
{
int *p1,*r1;
med = median(p,r);
split(p,r,p1,r1);
if(largest<*r1-*p1+1)
{
largest = *r1-*p1;
element = med;
}
if(*p1-1>largest)
mode(p,*p1-1);
if(r-*r1>largest)
mode(*r1+1,r);
}

void main()
{
int n,i,j;
FILE *fp1,*fp2;
fp1 = fopen("input.txt","r");
if(fp1==NULL)
{
printf("error\n");
return;
}
fscanf(fp1,"%d",&n);
printf("the quantuty of the number %d\n",n);
i = 0;
while(fp1!=NULL)
{
fscanf(fp1,"%d",&a[i]);
i++;
if(i>=n)
break;
}
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
printf("\n");
fclose(fp1);
mode(0,n);
fp2 = fopen("output.txt","w");
if(fp2==NULL)
{
printf("error\n");
}
fprintf(fp2,"%d\n%d",element,largest);
fclose(fp2);
}

Answer 2

要哪种语言的呀？

Answer 3

要哪种语言的呀？