1907 - 众数问题
给定含有n 个元素的多重集合S，每个元素在S 中出现的次数称为该元素的重数。多重
集S 中重数最大的元素称为众数。
例如，S={1，2，2，2，3，5}。
多重集S 的众数是2，其重数为3。
编程任务：
对于给定的由n 个自然数组成的多重集S，编程计算S 的众数及其重数。
Input
输入的第1 行多重集S 中元素个数n；接下来的n 行中，每行有一个自然数。
Output
程序运行结束时，将计算结果输出。
输出有2 行，第1 行给出众数，第2 行是重数。
Examples
Input
6 1 2 2 2 3 5
Output
2 3
Hint
利用中位数，将数组分为两段，对两段进行分治求解。
Solution C
#include <stdio.h> #include <malloc.h> void main() { int n,*a,i,j,p,zhongshu,chongshu=0; scanf("%d",&n); a=(int *)malloc(sizeof(int)*n); for(i=0;i<n;i++) scanf("%d",&a[i]); zhongshu=a[0]; for(i=0;i<n;i++) { for(j=0;j<i;j++) if(a[j]==a[i]) break; if(j!=i) continue; p=0; for(j=i;j<n;j++) if(a[j]==a[i]) p++; if(p>chongshu) { chongshu=p; zhongshu=a[i]; } } printf("%d\n%d\n",zhongshu,chongshu); free(a); }
Solution C++
#include<iostream> using namespace std; void search(int b[],int j){ int c[100]={0}; for(int k=0;k<j;k++){ for( int m=k+1;m<=j;m++){ if(b[k]==b[m]) c[k]+=1; } } int max=c[0]; for(int n=0;n<=j;n++) { if(c[n]>=max) max=c[n]; } for(int l=0;l<=j;l++) { if(c[l]==max) cout<<b[l]<<"\n"<<max+1; } } int main(){ int a[100],i,p=0; cin>>i; while(p<i){ cin>>a[p]; p++; } search(a,p); }
Hint
利用中位数，将数组分为两段，对两段进行分治求解。