C语言/数据结构算法题解：Boyer-Moore投票算法——找出数组中出现次数超过一半的数字（众数）

问题描述小R从班级中抽取了一些同学每位同学都会给出一个数字。已知在这些数字中有且只有一个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。输入格式输入为一个整型数组array数组长度n满足约束1 ≤ n ≤ 10000数组中的每个元素均为整数且满足-1000 ≤ array[i] ≤ 1000输出格式返回出现次数超过一半的数字注意题目保证有且只有一个数字满足条件无需考虑多个解或无解的情况程序代码#include stdio.hint majorityElement(int* array, int arraySize) {int candidate 0;int count 0;for (int i 0; i arraySize; i) {if (count 0) {candidate array[i];count 1;} else if (array[i] candidate) {count;} else {count--;}}return candidate;}int main() {int test1[] {1, 3, 8, 2, 3, 1, 3, 3, 3};int test2[] {5, 5, 5, 1, 2, 5, 5};int test3[] {9, 9, 9, 9, 8, 9, 8, 8};printf(%d\n, majorityElement(test1, 9));printf(%d\n, majorityElement(test2, 7));printf(%d\n, majorityElement(test3, 8));return 0;}#include stdio.h int majorityElement(int* array, int arraySize) { int candidate 0; int count 0; for (int i 0; i arraySize; i) { if (count 0) { candidate array[i]; count 1; } else if (array[i] candidate) { count; } else { count--; } } return candidate; } int main() { int test1[] {1, 3, 8, 2, 3, 1, 3, 3, 3}; int test2[] {5, 5, 5, 1, 2, 5, 5}; int test3[] {9, 9, 9, 9, 8, 9, 8, 8}; printf(%d\n, majorityElement(test1, 9)); printf(%d\n, majorityElement(test2, 7)); printf(%d\n, majorityElement(test3, 8)); return 0; }运行结果