用c语言输入一组数中出现次数多于或等于总数3的数
以下是一种可能的解法:
#include <stdio.h>
int main() {
int n;
printf("请输入整数个数:");
scanf("%d", &n);
int nums[n];
printf("请输入%d个整数:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &nums[i]);
}
int count = 0;
int candidate1 = 0, candidate2 = 0;
for (int i = 0; i < n; i++) {
if (nums[i] == candidate1) {
count++;
} else if (nums[i] == candidate2) {
count--;
} else if (count == 0) {
candidate1 = nums[i];
count = 1;
} else if (count == 1) {
candidate2 = nums[i];
count = 2;
} else {
count--;
}
}
count = 0;
for (int i = 0; i < n; i++) {
if (nums[i] == candidate1) {
count++;
}
}
if (count >= n / 3) {
printf("%d ", candidate1);
}
count = 0;
for (int i = 0; i < n; i++) {
if (nums[i] == candidate2) {
count++;
}
}
if (count >= n / 3) {
printf("%d ", candidate2);
}
return 0;
}
解释:
- 首先从标准输入读入整数个数
n和一组整数存储到数组nums中。 - 使用摩尔投票算法(Moore Voting Algorithm)找出两个可能的候选数。该算法的思想是,如果一个数的出现次数超过了一半,那么用该数替换掉另一个数,最后剩下的一定是要找的数。这里稍作修改,找出两个可能的候选数。
- 再次遍历数组
nums,分别统计这两个候选数的出现次数。如果某个数的出现次数大于或等于n/3,就输出该数。 - 最后返回 0 表示程序正常结束
原文地址: https://www.cveoy.top/t/topic/e9a1 著作权归作者所有。请勿转载和采集!