首页 > 试题广场 >

已知一个整数序列A=(a0，a1，...an-1),其中0≤

[问答题]

已知一个整数序列A = ( a₀，a₁，...a_n-1),其中0≤a_i＜n（0≤i＜n）。若存在a_p1=a_p2=···=a_pm=x，且m>n/2（0＜p_k＜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中的几个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：

(1) 给出算法的基本设计思想

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

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

汪宁海

int main_elem(int A[],int n)
{
    if(n==0)return -1;
    if(n==1)return A[0];
    int i=0,count=1,temp=A[0];
    for(i=1;i<n;i++)
    {
         if(A[i]==temp)count++;
         else count--;
          if(count==0)
          {
              temp=A[i];
              count=1;
          }
    }
    count=0;
    for(i=0;i<n;i++)
    {
        if(A[i]==temp)count++;
        if(count>n/2)return temp;
    }
    return -1;
}

发表于 2021-12-17 14:35:06 回复(0)