一組資料中,出現次數最多的數就叫這組資料的衆數。
如果有兩個或兩個以上個數出現次數都是最多的,那麼這幾個數都是這組資料的衆數。
如果所有資料出現的次數都一樣,那麼這組資料沒有衆數。
例1:1,2,3,3,4的衆數是3。
例2:1,2,2,3,3,4的衆數是2和3。
例3:1,2,3,4,5沒有衆數。
解法一:
#include <iostream>
#include <algorithm>
using namespace std;
int cnt[100000000];
int main()
{
int n;
cin >> n;
int a[n];
int maxCnt = 0;
for(int i = 0; i < n; i++)
{
cin >> a[i];
cnt[a[i]]++;
if(maxCnt < cnt[a[i]])
{
maxCnt = cnt[a[i]];
}
}
sort(a, a + n);
bool same = true;
for(int i = 0; i < n - 1; i++)
{
if(cnt[a[i]] != cnt[a[i + 1]])
{
same = false;
break;
}
}
if(same)
{
cout << "沒有衆數" << endl;
return 0;
}
int i = 0;
while(i < n)
{
if(cnt[a[i]] == maxCnt)
{
cout << "衆數:" << a[i] << ",出現的次數:" << cnt[a[i]] << endl;
}
i += cnt[a[i]];
}
return 0;
}
解法二:分治法
以a = {1, 2, 2, 2, 3, 3, 5, 6, 6, 6, 6},其中間元素為a[5] = 3。往左邊找等于3的最大位置,得到l = 4, a[l] = a[4] = 3;往右邊找不等于3(即大于3)的最小位置,得到r = 6, a[r] = a[6] = 5。則可以知道,最中間的3出現的次數cnt = r - l = 2次,即maxCnt = 2次。
接着進行分治:考慮元素3左邊的a[0] ~ a[l]部分和右邊的a[6] ~ a[10]部分。對這兩部分各自求cnt。得到左邊部分有3個2,右邊部分有4個6。則最終衆數是6,出現了maxCnt = 4次。
在遞歸的過程中,如果左邊或右邊的元素數量小于maxCnt,那就不需要再遞歸了。這是遞歸的終止條件。
// 用分治法求衆數
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
map<int, int> m;
// 左右兩邊與中間數相同的數的起始、終止界限
void split(int s[], int n, int &l, int &r)
{
int mid = n/2;
// 連續兩個for求與s[mid]相同的數有多少個
for(l=0; l<n; ++l)
{
if (s[l] == s[mid])
break;
}
for(r=l+1; r<n; ++r)
{
if (s[r] != s[mid])
break;
}
}
// num 衆數。 maxCnt 重數
void getMaxCnt(int &mid, int &maxCnt, int s[], int n)
{
int l, r;
split(s, n, l, r); // 進行分割。這個函數是本程式的關鍵
int num = n/2;
int cnt = r-l;
// 更新出現次數最多的數
if (cnt > maxCnt)
{
maxCnt = cnt;
mid = s[num];
m.clear();
m[mid] = maxCnt;
}
else if(cnt == maxCnt)
{
mid = s[num];
m[mid] = maxCnt;
}
// l表示mid左邊的個數。左邊的個數必須大于 maxCnt才有必要搜尋
if (l >= maxCnt)
{
getMaxCnt(mid, maxCnt, s, l);
}
// n-r表示mid右邊的個數, 右邊數組的起始位址要變更
if (n-r >= maxCnt)
{
getMaxCnt(mid, maxCnt, s+r, n-r);
}
}
int main(void)
{
int s[] = {1, 2, 2, 2, 3, 3, 5, 6, 6, 6, 6};
//int s[] = {20, 20, 30, 30};
int n = sizeof(s)/sizeof(s[0]);
sort(s, s + n);
int maxCnt = 0;
int num = 0;
getMaxCnt(num, maxCnt, s, n);
map<int, int>::iterator it;
int sum = 0;
for(it = m.begin(); it != m.end(); it++)
{
sum += it->second;
}
if(sum == n) // 唯一沒有衆數的情景
{
cout << "沒有衆數" << endl;
}
else
{
for(it = m.begin(); it != m.end(); it++)
{
cout << "衆數:" << it->first << ",出現次數:" << it->second << endl;
}
}
return 0;
}