众数问题给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。

例如，S={1,2,2,2,3,5}。多重集S的众数是2，其重数为3。对于给定的由n个自然数组成的多重集S，计算S的众数及其重数。

代码借鉴了别人写的，但他写的好像是错的。

分治法(经过排序)：（不排序的以后再看看）

1.先快速排序（升序降序都一样）

2.找到中位数，并记录其个数，与众数mid(假的，就是还没完全找到)的个数（初值为0）进行比较，

大于则将当前找到的中位数记为众数mid(假的) 否则mid(假的)不变。

（不管mid变没变）

然后先将当前中位数的左区间的个数和当前中位数的个数相比，大于则说明左区间中可能存在个数更多的数，

用分治法求左区间的众数（不用排序），小于则说明左区间中不存在个数更多的数。

再然后先将当前中位数的右区间的个数和当前中位数的个数相比，大于则说明右区间中可能存在个数更多的数，

用分治法求左区间的众数（不用排序），小于则说明右区间中不存在个数更多的数。

3.当递归结束则mid（假的）变成mid(真的)

为什么靠找中位数能间接找到众数？

对于一个排好序的数列，如果众数的个数大于总数的一半，则中位数一定是众数。

如果小于总数的一半，则有三种情况

1.众数在左半边（这里考虑众数个数大于总数的1/4，少于的后面会说），则左半边的中位数一定是众数。

2.众数在右半边（这里考虑众数个数大于总数的1/4），则右半边的中位数一定是众数。

3.众数在两边都占了。（这也是最麻烦的）

这时，我们就先认为中位数是这个区间的众数，并且找到这个中位数的区间，和其的左右区间共三个区间。

找到左右区间的众数个数与当前的众数个数进行比较，个数多的就记为数列的众数。

按照上方的方法找左右区间的众数。（这也是分治的含义）

我们可以发现，在递归的最后，区间的众数的个数肯定会大于总数1/4，所以一定可以找到这个区间的众数。

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

//写这个方便输入数据
//注意以\n结尾 不要在\n前多打了空格
template <typename T>
void read_in(std::vector<T>& x)
{
	T i;
	while (std::cin >> i && getchar() != '\n')
		x.push_back(i);
	x.push_back(i);
}
template <typename T>
void read_out(std::vector<T>& x)
{
	for (auto i : x)
		std::cout << i << ' ';
}

//正片

//这个函数用来求中位数的个数（通过定位left0和right0的值间接求得）
template <typename T>
void splid(vector<T> s, int& left0, int& right0, int left, int right)
{
	//由于right是作为众数串的结尾的下标
	//计算mid时要注意加1
	//例如
	//下标（0~11）中间的数应该为6或7(这里取小值)
	//如果（0+11）/2则mid为5  （0+11）/2 +1则mid为6
	//下标（0~10）中间的数应该为6
	//如果（0+10）/2则mid为5  （0+10）/2 +1则mid为6
	int mid = (left + right + 1) / 2;//计算区间中位数
	for (left0 = left; left0 <= mid; left0++)//定位众数串的左端
	{
		if (s[left0] == s[mid])//如果相等则说明定位到了
			break;
	}
	for (right0 = left0 + 1; right0 <= right; right0++)//定位众数串的右端
	{
		if (s[right0] != s[mid])//如果相等则说明定位到了
			break;
	}
	right0--;
    //这里是为了使得right0对应到众数串的最后一位而不是下一位（方便后面确定区间）
	//left0和right0可能相等
}
template <typename T>
void Mode(T& mid, int& MaxCnt, std::vector<T> s, int left, int right)
{
	int left0;
	int right0;
	splid(s, left0, right0, left, right);//定位left0和right0的值
	int cnt = right0 - left0 + 1;//表示众数串的长度（即众数数量）
	//left0和right0可能相等
	if (cnt > MaxCnt)
	{
		MaxCnt = cnt;//表示众数串的长度（即众数数量）
		mid = s[left0];//这里随便取left0或者right0因为对应的值都一样
	}
	if (left0 - left > MaxCnt)//表示众数串的左端到区间的左端的距离（即左边数组的个数）
	{
		Mode(mid, MaxCnt, s, left, left0 - 1);
	}
	if (right - right0 > MaxCnt)//表示众数串的右端到区间的右端的距离（即右边数组的个数）
	{
		Mode(mid, MaxCnt, s, right0 + 1, right);
	}
}
template <typename T>
T mode(std::vector<T> x)//没用引用 防止改变原容器
{
	//分治法求众数
	//先升序排序 sort();
	sort(x.begin(),x.end());
	T result = 0;//记录众数
	int MaxCnt = 0;//记录众数的个数
	//通过left和right定位区间长度
	//参数含义
//(众数(目标)，众数个数(用于比较数的数量)，容器，首元素下标(区间左端)，尾元素下标(区间右端))
	Mode(result, MaxCnt, x, 0, (int)x.size() - 1 );
	return result;
}
int main()
{
	vector<int> a;
	//vector<double> a;
	//vector<float> a;
	read_in(a);
	sort(a.begin(), a.end());
	cout << "a(升序排列):";
	read_out(a);
	cout <<endl<<"a的众数:";
	cout << mode(a)<<endl;
	return 0;
}

结语：

代码我试过了，暂时没发现错误，如有错误，欢迎指正!

#学习记录#

找众数

全站热榜