问题描述
小R从班级中抽取了一些同学，每位同学都会给出一个数字。已知在这些数字中，有且只有一个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。
输入格式：
- 输入为一个整型数组 array
- 数组长度 n 满足约束：1 ≤ n ≤ 10000
- 数组中的每个元素均为整数，且满足：-1000 ≤ array[i] ≤ 1000
输出格式：
- 返回出现次数超过一半的数字
注意：
- 题目保证有且只有一个数字满足条件，无需考虑多个解或无解的情况
程序代码：
#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;
}
#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;
}
运行结果：
