数据结构-线性表-应用题-2.2-12

1）算法的基本设计思想：依次扫描数组的每一个元素，将第一个遇到的整数num保存到c中，count记为1，若遇到的下一个整数还是等于num,count++,否则count--,当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，反复该过程，直到扫描全部数组元素为止。获得最终的候选主元素，但此时还没完成，出现次数还要过半才行，判断c中元素是否是真正的主元素，再次扫描该数组统计c中元素出现的次数，再进一步进行判断。

2）c语言描述：

int majority(int A[],int n){int i,c,count=1;c=A[0];//选出候选元素for(i=1;i<n;i++){if(A[i]==c){count++;}else if(count>0)count--;else{c=A[i];count=1;}}//统计候选元素出现次数if(count>0){for(i=count=0;i<n;i++){if(A[i]==c)count++;}}return (count>n/2)?c:-1; 
}

3）时间复杂度O(n),空间复杂度O（1）