标签：count map 数字 candidate int length 投票 数组 input

include <stdio.h>

// 找到数组中出现次数超过一半的数字
int findMostFrequent(int* input, int length) {
// 候选数字初始化为数组第一个元素
int candidate = input[0];
// 计数初始化为 1
int count = 1;

// 遍历数组
for (int i = 1; i < length; i++) {
    // 如果当前数字与候选数字相同，计数加一
    if (input[i] == candidate) {
        count++;
    } else {
        // 如果不同，计数减一
        count--;
        // 当计数为 0 时，更换候选数字
        if (count == 0) {
            candidate = input[i];
            count = 1;
        }
    }
}

// 进行第二次遍历，验证 candidate 是否真的出现次数超过一半
count = 0;
for (int i = 0; i < length; i++) {
    // 如果当前数字与候选数字相同，计数加一
    if (input[i] == candidate) {
        count++;
    }
}
// 如果计数超过数组长度一半，返回候选数字
if (count > length / 2) {
    return candidate;
} else {
    return -1; // 这里假设不存在满足条件的数字会返回 -1，实际上题目保证一定存在
}

}

int main() {
int input[] = {3, 4, 3, 5, 3, 6, 4, 7, 3};
int length = sizeof(input) / sizeof(input[0]);
int result = findMostFrequent(input, length);
printf("%d\n", result);
return 0;
}

标签：count,map,数字,candidate,int,length,投票,数组,input
From： https://www.cnblogs.com/zsh260439/p/18601086