我在C/C++论坛看到这个问题了。
如果元素是整型而且范围可以接受就好办。我这样想的~

有些猜想，
出现半数以上的那个数，连续出现的次数一定最多。把重复出现的数字加入一个新数组B内。O(n)
有一种情况是a,b,a,c,a,d,a,e,a，没有连续出现的数字（或者有多个数字出现连续次数一样最多），那么半数以上的数字必然是第一个数字（和最后一个数字相同）。
假如有任何一个数字连续出现的次数比a大，那么a不可能是出现半数以上的数字。a,b,b,a,c,a,d,a

新数组B如果仍然该数字最多，那么该数字必然过半数。（相当于求原数组连续出现3次的数字）。再次把重复出现的数字加入一个新数组C。O(m), m <= n/2

求证:)

半数以上包括刚好半数吗？条件中已经确定了一定存在这样的元素吗？我按lutree1985的算法写一个，似乎是O(n)的：

int CountItem(DataType *a,int n,DataType item)//返回item的元素个数,O(n)
{
     int c=0;
     while(n--)
          if(CompareData(a[n],item)==0)
               ++c;
     return c;
}
void GetHal(DataType *a,int n,/*out:*/DataType &hal,int &num)
{
     if(n==0)
     {
          hal=DATANULL;
          num=0;
          return;
     }
     if(n==1)
     {
          hal=a[0];
          num=1;
          return;
     }
     DataType h1,h2;
     int n1,n2,mid;
     mid=n/2;
     GetHal(a,mid,h1,n1);
     n1=n1+CountItem(a+mid,n-mid,h1);
     if(n1*2>n)
     {
          hal=h1;
          num=n1;
          return;
     }
     GetHal(a+mid,n-mid,h2,n2);
     n2=n2+CountItem(a,mid,h2);
     if(n2*2>n)
     {
          hal=h2;
          num=n2;
          return;
     }
     hal=DATANULL;
     num=0;
}

这是按‘过半数’的条件编的，如果刚好半数也算的话还要再加一些。

设GetHal()的时间函数是T(n)，那么
T(n)=2T(n/2)+O(n)=2^(log<2,n>)T(1)+O(n)=O(n)

iakiak的猜想我觉得是对的，具体那个B数组怎么做的？