c++分治算法解决众数问题

野性酷女 2022-11-18 04:57 242阅读 0赞

# 众数问题 #

Description  
给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S=\{1，2，2，2，3，5\}。多重集S的众数是2，其重数为3。对于给定的由n 个自然数组成的多重集S，计算S的众数及其重数。如果出现多个众数，请输出最小的那个。

Input  
输入数据的第1行是多重集S中元素个数n（n<1300000）；接下来的n行中，每行有一个最多含有5位数字的自然数，。

Output  
输出数据的第1行给出众数，第2行是重数。

Sample  
Input  
6  
1  
2  
2  
2  
3  
5  
Output  
2  
3

思路：首先要对输入的数据进行排序，然后直接找到数组中间的那个元素a\[n/2\],查找它左边或者右边与它相等的元素，求出这个长度。中间的这一组数据将数组分成了左右两份，再对左边从0到第一个不等于a\[n/2\]的元素递归。对右边第一个不等于a\[n/2\]的元素开始递归，到这个数组的最后一个元素。如果左边的元素个数小于这个长度，则不用向左递归，因为左边不可能存在众数了。右边同理，这就是递归结束的条件。将每一次递归所得的结果比较，求出众数。

#include<iostream>
    #include <algorithm>
    using namespace std;
    int a[1300000];
    void cut(int a[] ,int length,int &left,int &right)   //将数组从中间分割成左右两块 
    { 
    	int mid=length/2;
    	for(left=0;left<length;left++)  //找到第一个等于a[mid]的值的下标 
    	{ 
    		if(a[left]==a[mid])
    		{ 
    			break;
    		}
    	}
    	for(right=left+1;right<length;right++)//找到第一个不等于a[mid]的值的下标 
    	{ 
    		if(a[right]!=a[mid])
    		{ 
    			break;
    		}
    	}
    } 
    void fenzhi(int a[],int &num,int &max,int length)
    { 
    	int mid=length/2;
    	int left=0;
    	int right=0;
    	int longs=0; 
    	cut(a,length,left,right);
    	longs=right-left;   //求值等于a[mid]的长度 
    	if(longs>max)     
    	{ 
    		max=longs;
    		num=a[mid];
    	}
    	if(max==longs)
        { 
            if(num>a[mid])
            { 
                num= a[mid];
            }
        }
    	if(left>max)   //递归 
    	{ 
    		fenzhi(a,num,max,left);
    	} 
    	if(length-right>max)
    	{ 
    		fenzhi(a+right,num,max,length-right);
    	} 
    }
    int main()
    { 
    	int n;
    	int b;
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{ 
    		cin>>a[i];
    	}
    	sort(a,a+n);  //排序 
    	  
    	int num=0;
    	int max=0;
    	fenzhi(a,num,max,n);
    	cout<<num<<endl;
    	cout<<max<<endl;
    }