[C++知识库]HNUST：主元素

题目描述

输入

输入由多组数据组成。
每组数据由二行组成，第一行是整数n(1<=n<=100000), 第二行是n个空格分开的整数，它们的值位于区间[0,1000000000]。
题目保证60%的数据n的值不超过20。

输出

每一组输入数据输出一行。如果存在满足条件的x，则输出，否则输出-1。

样例输入?Copy

3
3 2 3
8
0 5 5 3 5 7 5 5
8
0 5 5 3 5 1 5 7

样例输出?Copy

3
5
-1

?方法1（计数法）

#include <stdio.h>
#include <stdlib.h>
 
int main ()
{
    int n,i,m,f,s,t,max1,max2,k;
    while (scanf("%d",&n)!=EOF)
    {
        int a[100]={0};
        f=0;s=0;t=n;max1=0;k=n/2;
        while (t--)
        {
            scanf("%d",&m);
            if (m<=20&&m>=0)
            {
                a[m]++;
                if (a[m]>max1)
                {
                   max1=a[m];max2=m;
                }
            }
         }
        if (max1>k)
        {
            f=1;
            printf("%d\n",max2);
        }
        if (f==0) printf("-1\n");
    }
    return 0;
}

这种只有60%的正确率

方法2（抵消法）

?
#include <stdio.h>
#include <stdlib.h>
 
int Majority ( int A[], int n )
{
 int i,c,count=1;//c用来保存候选主元素，count用来计数
  c=A[0]; //设置A[0]为候选主元素
  for(i=1;i<n;i++)
 {
      if(A[i]==c) count++;//对A中的候选主元素进行计数
      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++;
        }
    }
  if(count>n/2)  return c;//确认候选主元素
  else return -1;//不存在主元素
}
 
void main()
{
    int s[100001],m,i;
    while (scanf("%d",&m)!=EOF)
    {
        for (i=0;i<m;i++)
        {
            scanf("%d",&s[i]);
        }
        printf("%d\n",Majority(s,m));
    }
}

?