菜鸡学C语言之摸鱼村村长

题目描述

摸鱼村要选村长了！

选村长的规则是村里每个人进行一次投票，票数大于人数一半的成为村长。

然鹅摸鱼村的人都比较懒，你能帮他们写一个程序来找出谁当选村长吗？

（每名村民的编号都是一个int范围内的整数）

输入

多行，每行一个数字(int范围内)

输出

输出出现次数超过总数一半的数字。(保证一定有解)

输入样例

输出样例

题目链接：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 ;

}

巴特西