题目：
- 整数数组，包含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);
}
