众数04.cpp

算法分析与设计之众数 算法分析与设计 众数

#include<stdio.h>

void QuickSort(int a[],int p,int r);
int Partition(int a[],int p,int r);

int main()
{
	int n;
	int s[100];
	int i,count=1,max=1,max_num,num;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&s[i]);
	QuickSort(s,1,n);
	num=s[1];
	max_num=s[1];
	for(i=1;i<n;i++)
	{
		if(s[i]==s[i+1])
		{
			count=count+1;
			if(count>max)
			{
				max=count;
				max_num=num;
			}
			else if(count==max)
				if(max_num>num)
					max_num=num;
		}
		else
		{
			num=s[i+1];
			count=1;
		}
	}
	printf("\n%d\n%d\n",max_num,max);
	return 0;
}


void QuickSort(int s[],int p,int r)
{
	int q;
	if(p<r)
	{
		q=Partition(s,p,r);
		QuickSort(s,p,q-1);
		QuickSort(s,q+1,r);
	}
}

int Partition(int s[],int p,int r)
{
	int i=p,
		j=r+1;
	int temp;
	int x=s[p];
	while(1){
		while(s[++i]<x);
		while(s[--j]>x);
		if(i>=j) break;
		temp=s[i];
		s[i]=s[j];
		s[j]=temp;
	}
	s[p]=s[j];
	s[j]=x;
	return j;
}