寻找多数元素

题目：寻找多数元素班级：姓名：学号：一、问题描述令A[1..n]是一个整数序列，A中的整数a如果在A中出现的次数多于/2n，那么a称为多数元素。例如，在序列2,2,2,8,2,4,3,2中，2是多数元素，因为8个元素中它出现5次。当然多数元素要么不存在，要么就只有一个。二、算法输入输出输入：n个元素的数组A[1…n]。输出：若存在多数元素，则输出；都则输出none!三、算法描述解决这个问题有好多方法，其中蛮力方法就是把序列中的每个元素和其他每个元素比较，并且对每个元素计数，如果某个元素的计数大于/2n，就可以断言它是多数元素；否则，在序列中就没有多数元素。但是这样的比较次数是2(1)/2()nnn，这种方法的代价太昂贵。比较有效的算法是先对这些元素排序，并且计算每个元素在序列中出现多少次。这在最坏情况下的代价是(log)nn。因为在最坏情况下，排序这一步需要(log)nn次比较。但是上述的几种方法都存在着各种弊端，本程序中所用的程序的算法是一种比上面算法都要高效的算法，它用的比较次数要少得多。有观察结论为“在原序列中去除两个不同的元素后，那么在原序列中的多数元素在新序列中还是多数元素”。算法步骤如下：将计数器置1，并令[1]cA，从[2]cA开始，逐个地扫描元素，如果被扫描的元素和c相等，则计数器加1；如果元素不等于c，则计数器减1；如果所有的元素都已经扫描完毕并且计数器大于0，那么返回c作为多数元素的候选者。如果在c和[]Aj(1)jn比较时计数器为0，那么返回对于[1...]Ajn上的元素递归调用上述candidate过程。注意减少计数器就是观察结论中所述去除两个不同元素的思想的实现。得到候选者以后，需要验证候选者的准确性。这时候计数器置0，我们把得到的候选者c与原序列中的元素一个个一次比较，相等则计数器加1，比较结束后，如果计数器的值大于/2n，则候选者是真正的多数元素，否则不是。四、算法伪代码输入：n个元素的数组[1...]An。输出：若存在多数元素，则输出；否则输出none。MAJORITY:1.(1)2.03.14.[]15.6./27.ccandidatecountforjtonifAjcthencountcountendforifcountnthenreturncelsereturnnone过程()candidatem1.;[];12.03.14.[]15.16.7.8.(1)jmcAmcountwhilejnandcountjjifAjcthencountcountelsecountcountendwhileifjnthenreturncelsereturncandidatej五、程序代码#includestdio.h#includestdlib.hintc,count,j;intcandidate(intA[],intm,intn){j=m;c=A[m];count=1;while(jn&&count0){j++;if(A[j]==c)count++;elsecount--;}if(j==n)returnc;elsereturncandidate(A,j+1,n);}intmajority(intA[],intn){inti;c=candidate(A,0,n);count=0;for(i=0;in;i++){if(A[i]==c)count++;}if(count(n/2))returnc;elsereturn0;}voidmain(){inta[50];intp;intq;intm;printf(请输入数据个数:\n);scanf(%d,&m);printf(请输入数据:\n);for(p=0;pm;p++)scanf(%d,&a[p]);q=majority(a,m);if(q==0)printf(\nnone!\n);elseprintf(\n输入数据的多数元素为:%d\n,q);}由以上程序可得算法时间复杂度为O（n）。六、运行实例与结果分析1.有多数元素的情况2.无多数元素的情况下面根据第一个例子来说说程序递归过程：第一趟：j=m=0,c=A[0]=8,count=1,满足循环条件，j=1+0=1,，因为A[1]=9≠c，所以count=1-1=0，不满足循环条件且j≠n，返回candidate（2）。第二趟：j=m=2,c=A[2]=7,count=1,满足循环条件，j=2+1=3，因为A[3]=9≠c，所以count=1-1=0，不满足循环条件且j≠n，返回candidate（4）。第三趟：j=m=4,c=A[4]=9,count=1,满足循环条件，j=4+1=5，因为A[5]=6≠c，所以count=1-1=0，不满足循环条件且j≠n，返回candidate（6）第四趟：j=m=6,c=A[6]=9,count=1,满足循环条件，j=6+1=7=n，循环结束，返回候选者c的值9。递归结束，执行检验程序，发现count=43，所以得到原序列的多数元素9，输出结果，程序结束。