衆數和重數C++求解

問題描述

給定含有n個元素的多重集合S，每個元素在S中的次數稱為該元素的重數。多重集S中重數最大的元素稱為衆數。例如，S={1,2,2,2,3,5}。衆數為2，其重數為3。

思路：

1. 先将數組排序
2. 找到數組中位于中間的數及其重數n
3. 如果左邊的元素個數大于n，那麼衆數可能在左邊出現，繼續向左做遞歸運算
4. 右邊同理

代碼編寫如下：

#include <iostream>
#include <algorithm>
using namespace std;

int num=0; //存儲衆數
int sum=0; //存儲重數

int count(int a[],int s,int e){//計算中間數出現的次數
    int n=a[(s+e)/2];
    int counts=0;
    for(int i=s;i<e;i++)  { 
         if(a[i]==n) 
              counts++;
    }
   return counts;
}

int start(int a[],int s,int e){ //找到中間數出現的位置
     int x=0;
     for(in   t i=s;i<e;i++)  {
        if(a[i]==a[(p+q)/2]) {
            x=i;
            break;
       }
    }
    return x;
}

void mode(int a[],int s,int e){
     int  tnum=(s+e)/2;	      
     int  tsum=count(a,s,e);	
     int left=start(a,s,e);     
     if(tsum>sum)  { 
	sum=tsum;           num=a[tnum];
     }
    if(q-(left+tsum)>sum) mode(a,left+tsum,e);
    if(left>sum) mode(a,s,left);
}

int main()
{
	int a[10]={2,1,3,2,5,2,3,3,3,3};
	cout<<mode(a,0,9)<<endl;
	return 0;
}