[P2397] yyy loves Maths VI (mode)

Link:

P2397 传送门

Solution：

（1）在这里记录一个小小的黑科技：摩尔投票法

（线性时间复杂度，$O(1)$的空间复杂度求众数）

从数组的第一个元素开始，假定它代表的群体的人数是最多的

设置一个计数器，在遍历时遇到不同于这个群体的人时就将计数器-1，遇到同个群体的人时就+1

只要在计数器归0时就重新假定当前元素代表的群体为人数最多的群体再继续遍历

那么到了最后，计数器记录的那个群体必定是人最多的那个群体

其实就是抵消的思想嘛，记录当前有可能为众数的数，思想还是不错的

 

 

（2）这题还有一个挺妙的算法：记录二进制中每一位出现的次数，最后累加出现次数超过$n/2$的数位

将原数的（个数）关系转化到每一位，好像还挺常用的?

Code:

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int n,x,cur=,cnt=;

    scanf("%d",&n);

    while(n--)

    {

        scanf("%d",&x);

        if(!cnt) cnt++,cur=x;

        else if(x!=cur) cnt--;

        else cnt++;

    }

    printf("%d",cur);

    return ;

}

摩尔投票法

#include <bits/stdc++.h>

using namespace std;

int n,x,cnt[],res;

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&x);

        for(int dgt=;x;x>>=,dgt++)

            if(x&) cnt[dgt]++;

    }

    for(int i=;i>=;i--)

        if(cnt[i]>n/) res+=(<<i);

    printf("%d",res);

    return ;

}

位运算法