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