数据结构-线性表-应用题-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;i0)
        count--;
        else{
            c=A[i];
            count=1;
        }
    }
    //统计候选元素出现次数
    if(count>0){
        for(i=count=0;in/2)?c:-1; 
}

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