首页 > 代码库 > 众数的求法

众数的求法

2024-10-30 06:17:01   205人阅读

★问题描述：
给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。
例如，S={1，2，2，2，3，5}。
多重集S的众数是2，其重数为3。
★编程任务：
对于给定的由n个自然数组成的多重集S，编程计算S的众数及其重数。
★数据输入：
输入数据由文件名为input.txt的文本文件提供。文件的第1行多重集S中元素个数n；接下来的n行中，每行有一个自然数。
★结果输出:
程序运行结束时，将计算结果输出到文件output.txt中。输出文件有2行，第1行给出众数，第2行是重数。
输入文件示例   输出文件示例
input.txt       output.txt
6              2
1              3
2
2
2
3
5 
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

1、数组的众数求法

 

这回是对上次发帖后改用分治法解决的，还有待改进之处。

  1. #include<iostream>  
  2. #include<fstream>  
  3. using namespace std;  
  4. //结构体用来保存众数的元素与重数  
  5. typedef struct  
  6. {  
  7.     int element;//元素  
  8.     int sum;//重数  
  9. }zs;  
  10. //记录中位数的起始下标  
  11. typedef struct  
  12. {  
  13.     int low;  
  14.     int high;  
  15. }node;  
  16. //快排  
  17. zs x;  
  18. //int data=http://www.mamicode.com/1;
  19. void sort(int a[],int s,int t)//对a[s]到a[t]的元素排序  
  20. {  
  21.     int i=s,j=t;  
  22.     int temp;  
  23.     if(s<t)//区间里至少存在一个元素的情况  
  24.     {  
  25.         temp=a[s];//用区间的第一个元素做基准  
  26.         while(i!=j)//区间两端交替向中间扫描，知道I=J  
  27.         {  
  28.             while(j>i&&a[j]>temp)  
  29.                 j--;//从右向左扫描，找到第一个小于temp的a[j]  
  30.             if(i<j)//表示找到a[j],则a[i],a[j]交换  
  31.             {  
  32.                 a[i]=a[j];  
  33.                 i++;  
  34.             }  
  35.             while(i<j&&a[i]<temp)  
  36.                 i++;//从左向右扫描，找到第一个大于temp的a[i]  
  37.             if(i<j)//表示找到a[i],则a[i],a[j]交换  
  38.             {  
  39.                 a[j]=a[i];  
  40.                 j--;  
  41.             }  
  42.         }  
  43.         a[i]=temp;  
  44.         sort(a,s,i-1);//对左递归  
  45.         sort(a,i+1,t);//对右递归  
  46.     }  
  47. }  
  48. //中位数  
  49. int madian(int *a,int l,int r)  
  50. {  
  51.     int x=r+l+1;  
  52.     //  if(x%2)  
  53.     return a[x/2];//为奇数时  
  54.     //  else  
  55.     //      return (a[x/2]+a[x/2+1])/2;//为偶数时  
  56. }  
  57. //返回中位数的起始点  
  58. node spalit(int *a,int med,int l,int r)  
  59. {  
  60.     node m;  
  61.     m.low=l;m.high=r;  
  62.     for(int i=0;i<=r;i++)  
  63.     {  
  64.         if(med==a[i])  
  65.         {  
  66.             m.low=i;  
  67.             break;  
  68.         }  
  69.     }  
  70.     for(int j=r;j>=0;j--)  
  71.     {  
  72.         if(med==a[j])  
  73.         {  
  74.             m.high=j;  
  75.             break;  
  76.         }  
  77.     }  
  78.     return m;  
  79. }  
  80. //众数的重数求取  
  81. void mode(int *a,int l,int r)  
  82. {  
  83.       
  84.     if(l>=r)return;  
  85.     //x.sum=0;  
  86.     else  
  87.     {  
  88.         node n;  
  89.              int temp=0;  
  90.         int med;  
  91.         med=madian(a,l,r);  
  92.         n=spalit(a,med,l,r);  
  93.         temp=n.high-n.low+1;  
  94.         if(x.sum<temp)  
  95.         {  
  96.             x.element=med;  
  97.             x.sum=temp;  
  98.         }  
  99.         if(n.low-l>temp)//  
  100.         {  
  101.             if(x.sum<temp)  
  102.             {  
  103.                 x.element=med;  
  104.                 x.sum=temp;  
  105.             }  
  106.             mode(a,l,n.low-1);  
  107.         }  
  108.         if(r-n.high>temp)  
  109.         {  
  110.             if(x.sum<temp)  
  111.             {  
  112.                 x.element=med;  
  113.                 x.sum=temp;  
  114.             }  
  115.             mode(a,n.high+1,r);  
  116.         }  
  117.     }  
  118. }  
  119. void main()  
  120. {  
  121.     x.sum=0;  
  122.     int n;  
  123.     int *a;  
  124.     ifstream in("C://inputdate.txt");  
  125.     if(!in)  
  126.     {  
  127.     cout<<"the file can‘t open!"<<endl;  
  128.     }  
  129.     in>>n;  
  130.     a=new int[n];  
  131.     for(int i=0;i<n;i++)  
  132.     {  
  133.     in>>a[i];  
  134.          }  
  135.     sort(a,0,n-1);  
  136.     mode(a,0,n-1);  
  137.     cout<<x.element<<" "<<x.sum<<endl;  
  138.     delete []a;  
  139. }  

 第二种

 

void mode(int l,int r）{

int l1,r1;

int med=median(a,l,r);

split(a,med,l,r,l1,r1);

if(largest<r1-l1+1){

largest=r1-l1+1;

element=med;

}

if(l1-1>largest)

mode(1,l1-1);

if(r-r1>largest)

mode(r1+1,r);

}

 

3、利用先排序，然后统计个数。考虑时间效率，采用快排，count (统计个数)，maxCount(最多的个数),element(重数最大的数即众数)

 

4.可以利用散列法。

众数的求法


联系
我们