题目：

• 整数数组，包含n个元素
• 主元素 - 某个元素出现次数 > n/2
• 是否存在主元素
• 找出主元素

举个例子

数组：[1, 5, 1, 8, 1, 2, 1, 1, 3, 1]

包含6个1，出现次数超过了半数5

1就是主元素

数组：[1, 5, 9, 8, 1, 2, 1, 1, 3, 1]

包含5个1，出现次数不超过半数5

没有主元素

分析

主要逻辑包含两个要点

• 无论如何都需要统计元素的出现次数count，或者类似于统计的过程
• 主元素是哪个元素需要找到

最直观的思路 - 字典存储统计次数

用字典把元素当作key，value存储出现的次数

但是有需要遍历所有的存储key，比较各自出现次数大小

• 需要开辟额外的字典空间
• 事件复杂度会额外增加 O(n)

取巧部分

key - 主元素，默认取数组第一个当作key

反正需要统计次数

则在首次遍历数组的过程中，就统计count

我们可以不用统计具体每个元素出现的次数，既然主元素的出现次数超过 一半

• 则让主元素与其他元素竞争，遍历到是key，就count++，否则就 count--,直到为0
• 如果count == 0，没法--，就替换key，count = 1
• 如果key存在，那么key一定能竞争过其他所有元素，因为其他所有元素的次数之和不会超过数组元素数量的一半
• 这样只需要在遍历结束之后，判断count 是否大于0，否则不存在主元素
• 因为在遍历过程中一直保存着key，是个准key
• 遍历一次数组，统计key的次数，判断统计的次数 是否 大于 n/2
• 大于 n/2, 则key就是主元素了

这种方式比之前的字典方式，省去了空间复杂度

实现

void checkKeyElement(int array[], int n) {
    int count = 0;
    int key = array[0];
    
    for (int i = 0; i < n; i++) {
        if (array[i] == key) {
            count++;
        } else {
            if (count > 0) {
                count--;
            } else {
                key = array[i];
                count = 1;
            }
        }
    }
    
    if (count < 1) {
        printf("数组中不存在主元素\n");
        return;
    }
    count = 0;
    for (int i = 0; i < n; i++) {
        if (array[i] == key) {
            count++;
        }
    }
    if (count <= n / 2) {
        printf("数组中不存在主元素\n");
        return;
    }
    printf("数组中存在主元素 %i\n", key);
}