寻找数组中的主元素

已知一个整数序列A = (a0,a1,a2,...an-1),其中(0<= ai <=n),(0<= i<=n). 若存在ap1= ap2 = ...= apm = x,且m>n/2(0<=pk<n,1<=k<=m),则称x 为 A的主元素. 例如,A = (0,5,5,3,5,7,5,5),则5是主元素; 若B = (0,5,5,3,5,1,5,7),则A 中没有主元素,假设A中的n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出数组元素中的主元素,若存在主元素则输出该元素,否则输出-1.

示例:

输入：A = (0, 5, 5, 3, 5, 7, 5, 5)
输出：5

解题思路：

所谓主元素就是在一个数组中的某一个元素所出现的的次数大于大于数组长度的1/2

1. 选取候选的主要元素：依次扫描所给数组中的每一个整数，将第一个遇到的整数i保存到c中，记录i出现的次数为1，若遇到的下一个整数仍等于i，则计算器加1，否则计数器减1，当计数器减到0时，将遇到的下一个整数保存到x中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部元素。
2. 判断x中元素是否是真正的主元素：再次扫描该数组，统计x中元素出现的次数，若大于n/2，则为主元素，否则序列中不存在主元素。

代码：

typedef struct Node{
    int data;
    struct Node *next;
} Node;
typedef struct Node * LinkList;

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