分治法求众数和重数(含文件输入输出)

（可以列出所有众数）
代码：

#include<iostream>
#include<algorithm> 
#include<vector> 
using namespace std;
int mode=0,multiplicate=0;
vector<int> allmode;
void get_mode_and_multiplicate(int a[],int start,int end)
{
	if(end==start)return;//递归结束条件:当待考察序列只有一个元素,终止查看 
	int mid=(start+end)/2;
	int newmode=0,newmultiplicate=0,left=mid,right=mid,leftflag=1,rightflag=1;//次轮发现的众数个重数
	for(int i=mid-1;i>=start;i--)
	{
		if(a[i]!=a[mid])
		{
			left=i;leftflag=0;break;//找到从中间数向左边数第一个不相同的数 
		}
	}
	for(int i=mid+1;i<=end;i++)
	{
	    if(a[i]!=a[mid])
		{
			right=i;rightflag=0;break;//找到从中间数向右边数第一个不相同的数  
		}	
	} 
	if(leftflag==1)left=start;
	if(rightflag==1)right=end;
	//cout<<"left:"<<left<<" "<<"right:"<<right<<" ";
	newmode=a[mid];newmultiplicate=right-left-1;//次轮得到的众数候选重数候选
	if(leftflag==1&&rightflag==1)newmultiplicate+=2;
	else if(leftflag==1||rightflag==1)newmultiplicate+=1;
	//cout<<"nowmode:"<<newmode<<" "<<"nowmultiplicate:"<<newmultiplicate<<endl;
	if(newmultiplicate>multiplicate)//如果得到的新众数重数更大，更新众数和重数 
	{
		multiplicate=newmultiplicate;mode=newmode;allmode.push_back(mode);
	} 
	else if(newmultiplicate==multiplicate)allmode.push_back(newmode);
	get_mode_and_multiplicate(a,start,left);//继续在左边的待查数组里递归 
	get_mode_and_multiplicate(a,right,end);//继续在右边递归 
}
int main()
{
    int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a,a+n);
	get_mode_and_multiplicate(a,0,n-1);
	cout<<"最终结果："<<endl;
	if(multiplicate<=1)
	{
		cout<<"没有众数，所有元素都只出现了1次"<<endl;
		vector<int>().swap(allmode);//保存的数并不是众数已经没有用了，当数据量过大，释放vector内存 
	} 
	else if(multiplicate>1) 
	{
		cout<<"共有"<<allmode.size()<<"个众数"<<endl;
		cout<<"为：";
		for(int i=0;i<allmode.size();i++)cout<<allmode[i]<<" "; 
	}
	return 0;	 
} 

运行结果：


思路：
首先对数组进行排序，这样相同值的元素就挨在了一起，通过对某个元素进行向左向右查看是否有元素相同，就可判断当前元素共出现了多少次。不断地划分数组，每次都找到数组中的1个元素作为候选众数，以该元素出现次数为候选重数，把候选重数与当前保存的重数比较，如果更大，则更新当前保存的众数和重数，如果一样大说明目前有出现次数一样的众数，把它存入vector中保存起来。每次划分数组长度都减半，要处理的数组越来越短，直至数组里只有1个元素就结束排查了。(其实就是用了递归的方法)
（每次对半分让子问题规模尽量相等时间复杂度最小，也体现了分治法的思想）

步骤：
1.使用sort函数平均情况下时间复杂度只有nlogn(最差情况就比较差了，为n²)
2.首先判断一下当前待处理的数组需不需要处理，如果只有1个元素，肯定不是众数，不用再操作了直接结束。如果元素个数>1,则开始处理：
首先，找到当前待处理数组的中间值a[(start+end)/2]作为此次排查中的候选众数，该值出现的次数为候选重数。
左右两个循环来找到两边最近的与它不同的元素，标记一下两侧的不同元素的位置，则从标记处分成了左右新的两个短数组。
然后，此时两侧标记相减(不是单纯相减，有一点误差，自己举个例子算一下就可以调整了，不同情况下+1/-1/不变,代码中有注释)就是此轮的候选重数。
最后，比较候选重数和当前保存的重数(全局变量)进行判断：
(1)如果候选重数与其一样大，把当前这个数保存到vector中；
(2)如果候选重数更大，说明之前保存的众数都无效了，因为它们不是出现最多的数，∴清空vector，再将当前这个数保存到vector中；
(3)如果候选重数小，不用管，当前保存的数仍是目前出现最多的数；
3.对分出的左右两个数组继续2的操作，即判断数组中间位置的数是不是众数的操作，用递归来实现。

（文件型输入输出）代码：

#include<iostream>
#include<algorithm> 
#include<vector> 
#include<fstream>//用于文件输入输出 
using namespace std;
int mode=0,multiplicate=0;
vector<int> allmode;
void get_mode_and_multiplicate(int a[],int start,int end)
{
	if(end==start)return;//递归结束条件:当待考察序列只有一个元素,终止查看 
	int mid=(start+end)/2;
	int newmode=0,newmultiplicate=0,left=mid,right=mid,leftflag=1,rightflag=1;//次轮发现的众数个重数
	//找到从中间数向左边数第一个不相同的数
	for(int i=mid-1;i>=start;i--)
	{
		if(a[i]!=a[mid])
		{
			left=i;leftflag=0;break; 
		}
	}
	//找到从中间数向右边数第一个不相同的数 
	for(int i=mid+1;i<=end;i++)
	{
	    if(a[i]!=a[mid])
		{
			right=i;rightflag=0;break; 
		}	
	} 
	if(leftflag==1)left=start;//如果左边找不到不相同的数,就只好赋值为当前数组左起点 
	if(rightflag==1)right=end;//如果右边找不到不相同的数,就只好赋值为当前数组右终点
	newmode=a[mid];newmultiplicate=right-left-1;//次轮得到的众数候选重数候选
	if(leftflag==1&&rightflag==1)newmultiplicate+=2;
	else if(leftflag==1||rightflag==1)newmultiplicate+=1;
	if(newmultiplicate>multiplicate)//如果得到的新众数重数更大 
	{
		multiplicate=newmultiplicate;mode=newmode; //更新重数和众数 
		allmode.clear();allmode.push_back(mode);//原来vector中保存的众数失效,清空存入新值 
	} 
	else if(newmultiplicate==multiplicate)allmode.push_back(newmode);
	get_mode_and_multiplicate(a,start,left);//继续在左边的待查数组里递归 
	get_mode_and_multiplicate(a,right,end);//继续在右边递归 
}
int main()
{
	ifstream infile("input.txt",ios::in);  
	
	//读取元素个数n 
    int n;
	infile>>n;
	
	//读取元素 
	int a[n];
	for(int i=0;i<n;i++)infile>>a[i];
	
	sort(a,a+n);
	get_mode_and_multiplicate(a,0,n-1);
	
	ofstream outfile("output.txt",ios::out);
	if(multiplicate<=1) 
	{
		outfile<<"没有众数，所有元素都只出现了1次"<<endl;
		vector<int>().swap(allmode);//保存的数并不是众数已经没有用了，当数据量过大，释放vector内存 
	} 
	else if(multiplicate>1) 
	{
		outfile<<"共有"<<allmode.size()<<"个众数:";
		for(int i=0;i<allmode.size();i++)outfile<<allmode[i]<<" "; 
		outfile<<endl<<"出现次数为："<<multiplicate;
		cout<<"结果请在输出文件output中查看";
	}
	return 0;	 
} 

输入：

运行结果：

注：
1.如果题目有说保证输入的数据只有1个众数，就不需要vector数组来保存了，可以把代码中有关的部分都删掉，每次只要判断一下候选重数是不是比保存的重数大，如果是的话，更新一下重数和众数就可以了，代码会短很多~
2.另外输出部分当重数为1即没有众数的情况下我为了防止输入的数据量太大，把vector的内存释放了(swap()实现)，也可以删掉，代码又会短很多~
3.总体来说分治法和递归很相似，可以说分治是策略，递归是代码方法，分治用到递归

如有错误或不完善的地方，欢迎指出