#include <stdio.h>

int majority(int [], int, int);                 /* 确认候选值是不是主要元素 */
int primarykey(int arr[], int n)                /* 找出候选值 */
{
    int gal = 1;
    int key = arr[0];
    int i;
    for (i = 1; i < n; i++) {
        if (key == arr[i]) {
            gal++;
        }
        else
            gal--;
        if (gal == 0) {
            gal = 1;
            key = arr[i];
        }
    }
    return majority(arr, n, key);
}

int majority(int a[], int n, int key)
{
    int i;
    int sumkey = 0;
    for (i = 0; i < n; i++)
        if (a[i] == key)
            sumkey++;
    if (sumkey > n / 2)
        return key;
    else
        return 0;
}
int main(void)
{
    int a[] = {3, 3, 4, 3, 3, 4, 2, 4, 3};
    printf("%d\n", primarykey(a, 8));
    printf("%d\n", primarykey(a, 9));
    return 0;
}

啊啊