本文共 1087 字，大约阅读时间需要 3 分钟。

题目：已知一个整数序列A=（a0，a1，…，an-1），其中0≤ai<n(0≤i<n)。若存在ap1=ap2=…=apm=x且m>n/2（0≤pk<n，1≤k≤m），则称x为A的主元素。例如A=(0，5，5，3，5，7，5，5)，则5为主元素；又如A=(0，5，5，3，5，1，5，7)，则A中没有主元素。

假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

分析：由题目中定义，主元素个数必须大于所有元素个数的一半，也可以说，主元素的个数比非元素个数之和还要多。

答：

（1）算法思想：

选取备选主元素，用count记录主元素个数和其他元素个数的差。初始时count为1，第一个元素为主元素，遇到主元素，count+1，遇到其他元素，count-1，count为0时，主元素定义在前半部分不满足。如果存在主元素，必须在后半部分满足定义，所以直接舍弃前半部分。将当前扫描的下一个元素暂定为主元素，count重新记为1，直到扫描完所有数组。留下的那个元素有可能是主元素；统计上面得到的备选主元素的个数，验证是否满足主元素定义。

（2）算法实现：

int Majority(int A[],int n){    int i,c,count=1;            //c用来保存候选主元素，count用来计数    c = A[0];                   //设置A[0]位候选主元素    for(i=1;i
   
    0)         //处理不是候选主元素的情况                count--;            else{               //count=0，更换候选主元素，重新计数                c=A[i];                count=1;            }    if(count>0)        for(i=count=0;i
    
     n/2) return c;     //确认候选主元素    else return -1;             //不存在主元素}
    
   

（3）该算法时间复杂度为O(n)，空间复杂度为O(1)。

（如果上面的算法太难想，不用纠结最优解，能解出来最重要）

转载地址：http://teeii.baihongyu.com/