找出 A 的主元素

#include <stdio.h>
#include <stdlib.h>

//主元素问题  某个元素出现次数大于50%

//方法一：
//方法一思想：如果某元素是主元素的话 那么他与剩下的其他元素一一抵消的话他也会胜出；
int Majority_1(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++;                //依次遍历查找，找到的话个数加一
        else
        {
            if(count>0)
                count--;        //抵消
            else
            {
                c=A[i];
                count=1;        //count<0则更改候选主元素
            }
        }

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

}


//方法二：

int Majority_2(int B[],int n)
{//计数法。思想创建一个辅助数组M，数组长度为MAX(A[])；遍历数组，遇到重复的M[A[i]]增1；

    int mx,i,temp;
    mx=B[0];
    for(i=1;i<n;i++)        //找出数组中的最大值
    {
        if(mx<B[i])
            mx=B[i];
    }
    printf("mx=%d\n",mx);

    int M[mx+1];              //注意！！！ 数组大小是mx+1;

    for(i=0;i<=mx;i++)       //将数组M初始化为0
    {
        M[i]=0;
    }

    int L;
    for(i=0;i<n;i++)        //对元素计数
    {
        L=B[i];
        M[L]++;
    }

    int p;
    for(i=0;i<mx;i++)
    {
        temp=M[0];
        if(temp<M[i])
        {
            temp=M[i];
            p=i;
        }
    }

    if(temp>n/2)
        return p;
    else
        return -1;
}





//方法三
//使用冒泡排序

int BubbleSort(int C[],int n)
{
    int m=n-1;              //n个数需要排序n-1次
    int Flag=1;             //用来标记每一趟是否发生排序
    int temp,c,count;
    int j;
    while((m>0)&&(Flag==1))
    {
        Flag=0;
        for(j=0;j<m;j++)
            if(C[j]>C[j+1])
        {
            Flag=1;         //标记Flag表示本趟发生了排序
            temp=C[j];
            C[j]=C[j+1];
            C[j+1]=temp;

        }
        m--;                //每完成一趟，m减1
    }
    c=C[n/2];           // 改为(n+1)/2 考虑到奇数个数
    count=1;
    for(j=0;j<n;j++)
    {
        if(C[j]==c)
            count++;

    }


    if(count>n/2)
        return c;
    else
        return -1;

}

//主函数
int main()
{
    int n;
    int data;
    int q;
    printf("请输入数组长度：\n");
    scanf("%d",&n);
    int a[n];
    printf("请输入数组元素：\n");
    for(int i=0;i<n;i++)
    {
        scanf("%d",&data);
        a[i]=data;
    }
    printf("遍历数组：\n");
    for(int i=0;i<n;i++)
    {
        printf("%d\n",a[i]);
    }

    //q=Majority_1(a,n);
    q=BubbleSort(a,n);
    printf("主元素是：%d\n",q);
    return 0;


}

摩尔投票法求众数https://mabusyao.iteye.com/blog/2223195

//摩尔投票法求众数 
#include<iostream>
#include<iostream>
using namespace std;
int a[100]; 
int MoEr(int a[],int n)
{     int c=a[0];     int count=1;     for(int i=1;i<n;i++)     {         if(c==a[i])             count++;         else         {             count--;             if(count==0)                 c=a[i+1];         }     }     count=0;     for(int i=0;i<n;i++)     {         if(a[i]==c)             count++;     }     if(count>n/2)         return c;     else          return -1; }
int main()
{     int n;     cin>>n;     for(int i=0;i<n;i++)         cin>>a[i];     cout<<MoEr(a,n)<<endl;     return 0;     } 

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

算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。 然后重新计数， 确认 Num 是否是主元素。算法可分为以下两步：
① 选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数 Num 保存到 c 中，记录 Num 的出现次数为 1；若遇到的下一个整数仍等于 Num，则计数加 1，否则计数减 1； 当计数减到 0 时，将遇到的下一个整数保存到 c 中，计数重新记为 1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。
② 判断 c 中元素是否是真正的主元素：再次扫描该数组，统计 c 中元素出现的次数，若大于 n/2，则为主元素；否则，序列中不存在主元素。

（2） （2）算法实现：

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; / / 不存在主元素 
}