基礎(chǔ)算法題：
給定含有n個元素的多重集合S，每個元素在S中出現(xiàn)的次數(shù)稱為該元素的重數(shù)俱箱，多重集合S中重數(shù)最大的元素稱為眾數(shù)。例如灭必。多重集合S的眾數(shù)是2狞谱，其重數(shù)為3。要求對于給定的由n個自然數(shù)組成的多重集合S禁漓，計算S的眾數(shù)及其重數(shù)跟衅。
網(wǎng)絡(luò)上流傳著很多版本的算法思路，大多是使用分治法迭代或者遞歸來完成播歼。
但是對于這道題伶跷，可以使用更簡明的方法（雖然時間復(fù)雜度我沒有去比較，但是就思路來說秘狞，更容易解釋）
可以這樣理解：眾數(shù)可能不止有一個叭莫，但是重數(shù)肯定是只有一個的。所以選擇用一個數(shù)組來存儲眾數(shù)烁试，用一個變量來接收重數(shù)雇初。使用數(shù)組來存放集合。
#include<stdio>
#include<iostream>
using namespace std;
需要統(tǒng)計的是每個數(shù)字出現(xiàn)的次數(shù)减响，必然是需要遍歷整個數(shù)組靖诗，而且次數(shù)肯定是不止一次的，所以不如支示，先使用冒泡排序給整個數(shù)組排序
void bubblesort(int arr[], int n)
{
for (int i = 0; i < n; i++) {
//比較兩個相鄰的元素
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
}
}
}
}
排完序之后的數(shù)組在我們?nèi)搜劭磥硭坪跏悄芤谎劭闯鰜淼降啄男┦潜姅?shù)刊橘，哪個是重數(shù)，可是計算機并不是那么智能悼院。
我們需要在主函數(shù)中對數(shù)組進行刪減伤为，先定義一個虛擬的眾數(shù)，既然都已經(jīng)拍過序了据途，那么數(shù)組的首個元素當然是首選。從s[0]開始計數(shù)叙甸，定義一個index來計數(shù)颖医，每次遇到一個與s[0]相同的元素，便加1裆蒸，這時候便可以知道排序的好處熔萧，因為不必每次遍歷都完成整個數(shù)組的循環(huán)，節(jié)省了計算成本。
int main()
{
int s[0] = {1,2,5,8,3,5,8,7,12,4,2,6,7,2,1,4,5,2,7,3,45,67,2,4,6,3,1};
int n = sizeof(s) / sizeof(s[0]);
bubblesort(s,n);
cout<<endl;
for(int i = 0;i<n;i++)
{
cout<<s[i];
}
int maxCnt=0;
int maxnum[10];
int num=0;
cout<<endl;
int m = 0;
這里使用maxnum[]數(shù)組來接收可能出現(xiàn)的多個眾數(shù)佛致，使用maxCnt來接收最終的重數(shù)贮缕，使用Cnt來存放運行過程中出現(xiàn)的所有數(shù)字的重數(shù)。
接下來就是程序的關(guān)鍵俺榆，循環(huán)感昼。n是數(shù)組的長度，因為每次統(tǒng)計完元素的重數(shù)后罐脊，都需要將已經(jīng)統(tǒng)計過的元素刪除出數(shù)組定嗓，可是C++并沒有這種BIF，所以我們可以使用數(shù)組長度的自減和指針的移位來完成萍桌，每次長度都會減去Cnt個單位宵溅，直到n不大于maxCnt。這里要注意每次循環(huán)都要重置Cnt的值上炎，在循環(huán)里定義即可恃逻，同時記得要存入maxnum[]中的眾數(shù)。
while(n>=maxCnt)
{
int Cnt = 0;
num = s[0];
for(int j = 0;j<n;j++)
{
if(s[j]==num)
{
Cnt = Cnt+1;
}
else
{
break;
}
}
n = n-Cnt;
int index = 0;
for(index = 0;index<n;index++)
{
s[index] =s[index+Cnt];
cout<<s[index];
}
cout<<" "<<Cnt;
if(Cnt>=maxCnt)
{
maxCnt = Cnt;
maxnum[m]= num;
m=m+1;
}
cout<<" "<<maxCnt;
cout<<endl;
}
接著就是輸出了藕施，我這里是測試時寫的輸出辛块，比較簡單：
cout<<endl;
cout<<endl;
for(int t = 0;t<m;t++)
{
cout<<"眾數(shù)為"<<maxnum[t]<<" ";
}
cout<<endl;
cout<<"重數(shù)為"<<maxCnt;
完整代碼如下，可以使用VC++6.0润绵，或者vs尘盼，但是要注意變量定義的問題，vs總是容易報錯。底桂。
//author named sunxth
//IDE vs2017
#include <iostream>
#include <cstdio>
using namespace std;
void bubblesort(int arr[], int n)
{
for (int i = 0; i < n; i++) {
//比較兩個相鄰的元素
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
}
}
}
}
int main()
{
int s[] = {1,2,3,1,2,4,5,5,3,1,1,2,2,5,3,7,4,2,6,1,6,6,1};
int n = sizeof(s)/sizeof(s[0]);
bubblesort(s,n);
cout<<endl;
for(int i = 0;i<n;i++)
{
cout<<s[i];
}
int maxCnt=0;
int maxnum[10];
int num=0;
cout<<endl;
int m = 0;
while(n>=maxCnt)
{
int Cnt = 0;
num = s[0];
for(int j = 0;j<n;j++)
{
if(s[j]==num)
{
Cnt = Cnt+1;
}
else
{
break;
}
}
n = n-Cnt;
int index = 0;
for(index = 0;index<n;index++)
{
s[index] =s[index+Cnt];
cout<<s[index];
}
cout<<" "<<Cnt;
if(Cnt>=maxCnt)
{
maxCnt = Cnt;
maxnum[m]= num;
m=m+1;
}
cout<<" "<<maxCnt;
cout<<endl;
}
cout<<endl;
cout<<endl;
for(int t = 0;t<m;t++)
{
cout<<"眾數(shù)為"<<maxnum[t]<<" ";
}
cout<<endl;
cout<<"重數(shù)為"<<maxCnt;
getchar();
return 0;
}
