文档介绍：⑴问题提出：
令A[l,2,-n]是一个整数序列，A中的整数a如果在A中出现的次数多余 III,那么a称为多数元素。例如在序列1,3,2,3,3,4,3中，3是多数元素，因为在7个元素中它出现了四次。有几个方法可以解决这个问题。蛮力方法是把每个元素和其他各个元素比较，并且对每个元素计数，如果某个元素的计数大于 III,就可以断定它是多数元素，否则在序列中就没有多数元素。但这样比较的次数是n(n-l)/2= 0(nz),这种方法的代价太昂贵了。比较有效的算法是对这些元素进行排序，并且计算每个元素在序列中出现了多少次。这在最坏情况下的代价是® (n 1。时】).因为在最坏情况下，排序这一步需要Q(n log n) 0另外一种方法是寻找中间元素，就是第E1元素，因为多数元素在排序的序列中一定是中间元素。可以扫描这个序列来测试中间元素是否是多数元素。由于中间元素可以在® (n)时间内找到，这个方法要花费® (n)时间。
有一个漂亮的求解方法，它比较的次数要少得多，我们用归纳法导出这个算法，这个算法的实质是基于下面的观察结论。
观察结论：在原序列中去除两个不同的元素后，原序列的多数元素在新序列中还是多数元素。
这个结论支持下述寻找多数元素候选者的过程。将计数器置1,并令c=A[l]o 从A[2]开始逐个扫描元素，如果被扫描的元素和c相等。则计数器加1,否则计 ,那么返回c作为多数元素的候选者。如果在c和A[j](l<j<n)比较式计数器为0,那么对A[j+1,… n]上的过程调用candidate过程。算法的伪代码描述如下。
⑵算法
Input: An array/\[l...n] of n elements;
Output: The majority element if it exists; otherwise none;
counts—0;
for j<—1 to n
if/\[/]=cthen count<^count+l;
end for;
if count>Ln/2j then return c;
else return none;
candidate(m)
j<—m; c<—/4[m]; count—1;
while j<n and count>0
J
if/\[/]=cthen count <^count+l;
else count <—count-1;
end while;
if j=n then return c;
else return candidate'+l);
(3)代码
#include<>
#include<>
int majority(int*A,int n);
int candidate(int m,int n);
int*A;
void mainQ
{
int i,d,n;
printf("please input number n \n");
scanf("%d",&n);
A =(int*) mallo c (siz eo f(int) *n);
for(i=0;i<n;i+ +)
scanf("%d",&A[i]);
d=majori