题目描述
摸鱼村要选村长了！
选村长的规则是村里每个人进行一次投票，票数大于人数一半的成为村长。
然鹅摸鱼村的人都比较懒，你能帮他们写一个程序来找出谁当选村长吗？
（每名村民的编号都是一个int范围内的整数）
输入
多行，每行一个数字(int范围内)
输出
输出出现次数超过总数一半的数字。(保证一定有解)
输入样例
1
1
12345678
2
1输出样例
1题目链接：https://buaacoding.cn/problem/1897/index
题目概要：多行数据（具体几行未知），从中选出超过半数的数据。（保证这个数据一定存在）
题目分析：
- 本题由于数据未知，而且数据量很大，所以试图开十分大的数组来卡数据的方式不是出题人的本意，因此需要找到一种“巧妙”的算法来实现
- 本题的重点在于找出超过半数的数据，请注意：不是出现次数最多的数据！当然，本题中出现次数最多的一定是超过半数的数据，但如果对别的题来说，只是要找到出现次数最多的数据，那么下面这种算法就无法实现了。
- 正如上面所分析：出现超过半数的数据，意味着其他所有数据出现的次数加起来也不如他多！
- 下面介绍两种非常巧妙的思路
思路一：
借助计算机中每个数的存储都是二进制的形式，int为32位整数，每位只有两种情况，即0或者1。因此，出现次数超过半数的数据对应的二进制位上的0和1一定是最多的。（可能说起来仍然不好表述，看到代码一定能懂）
#include<stdio.h>
int main()
{
int cnt[][] = {};
// int 32位数每位对应的数字
// cnt[i][0] 表示第i位为0； cnt[i][1] 表示第i位为1；
int a, ans = , i;
while(scanf("%d",&a)!=EOF){
for(i = ; i < ; i++)
if(&(a>>i))
cnt[i][]++;
else
cnt[i][]++;
}
for(i = ; i < ; i++)
// 判断超过半数的数据第i位的数字
if(cnt[i][] > cnt[i][])
ans|=(<<i);
printf("%d",ans);
return ;
}
#include<stdio.h>
int main(){
int cnt[][] = {};
int i, temp;
while(~scanf("%d", &temp)){
for(i = ; i < ; i++){
if(temp & )
cnt[i][]++;
else
cnt[i][]++;
temp = temp >> ;
}
}
int ans = ;
for(i = ; i >= ; i--)
if(cnt[i][] > cnt[i][])
ans = (ans << ) + ;
else
ans = ans << ;
printf("%d", ans);
return ;
}
其思路之精巧令人咋舌！
思路二：
最坏的情况就是出现次数最多的数据和其他数据都抵消了，最后仍能剩下它这组数据。
正常情况可能存在其他数据之间也相互抵消的情况，那么最后更是只剩下这组数据了。
#include<stdio.h>
int main() {
int cnt = , n, x;
while(~scanf("%d", &x)) {
if(cnt == )
// 全部抵消完成（回到最初的起点
n = x;
if(x == n) {
cnt++;
} else {
cnt--;
}
}
printf("%d", n);
return ;
}
其思路之精巧令人咋舌！
思路三：
朴素做法，虽然不是本题出题人本意，但利用数组保存数据也不失为一种思路。
（附：本学期做C语言助教，老师告诉我，将此题应用到实际生活中，宁肯多开空间，也不能丢失选票）
#include <stdio.h>
#include <stdlib.h> int a[]; int comp_int(const void *a, const void *b)
{
return *(int *)a-*(int *)b;
} int main()
{
int cnt = ;
while (scanf("%d", &a[cnt]) != EOF)
{
cnt++;
}
cnt--;
qsort(a+, cnt, sizeof(int), comp_int);
// 排序，排序完成后中间的数据一定是出现次数过半的数据
printf("%d", a[cnt / ]);
return ;
}