主元素问题（算法）

主元素问题的绝妙算法

已知一个数组的大小，并且其中存在一个数，出现的频率大于50%，则称其为该数组的主元素。用一个算法找出这个数，要求其时间复杂度尽可能低。（这个问题貌似还是计算机专业的考研试题啊）

解法：
声明一个变量count = 0，声明一个常量size等于数组大小。
假设该数组的第一个元素a(1)为主元素，让其与a(2)进行比较，若相同，则使变量count+1，若不同，则count-1。然后继续比较a(3)。以此类推。

当与a(n)比较后，count = -1时，将count重新归为0，并重新假设a(n+1)为主元素，并继续与a(n+2)作比较。

当count>=(size-m)/2时，此时假设的主元素a(m)即为实际的主元素。
或遍历完整个数组后，当前假设的主元素为实际主元素。

这个算法的时间复杂度最大才O(N)，看书看到这一段时令我顿时拍案叫绝啊。其核心思想在于：对于这样一个数组，去除掉任意两个不相等的数，剩下的数中，主元素的出现频率仍然大于50%。而使用count来进行加减计数，当count=0时，必然是偶数个数与假设的主元素进行了比较，且其中有一半与假设数相同一半与假设数不同（当count=-1时，加上假设数的集合，也满足该条件）。
代码如下：

//主元素问题
#include <stdio.h>

int main()
{
    int a[20];
    int n;
    int cnt=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int flag=1,i;
    for(i=1;i<=n-1;i++)
    {
        if(a[flag]==a[i+1])
            cnt++;
        else
            cnt--;
        if(cnt==-1)
        {
            cnt=0;
            flag=i+1;
        }
        if(cnt>=(n-i)/2)
        {
            printf("main is %d\n",a[flag]);
            break;
        }
    }
    if(i==n)
        printf("main is %d\n",a[flag]);
    return 0;
}