Leetcode Majority Element系列摩尔投票法

先看一题，洛谷2397：

题目背景

自动上次redbag用加法好好的刁难过了yyy同学以后,yyy十分愤怒.他还击给了redbag一题,但是这题他惊讶的发现自己居然也不会,所以只好找你

题目描述

[h1]udp2:第一题因为语言性质问题，比赛结束后将所有c/c++的程序的内存调为2.2mb后重测。[/h1]

他让redbag找众数

他还特意表示,这个众数出现次数超过了一半

一共n个数,而且保证有

n<=2000000

而且每个数<2^31-1

代码

#include<bits/stdc++.h>

using namespace std;

inline int read(){

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

    return x*f;

}

int n,cnt,now,x;

int main(){

    scanf("%d",&n);

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

        scanf("%d",&x);

        if(x==now) cnt++;

        else if(cnt==) now=x,cnt++;

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

    }

    printf("%d\n",now);

    return ;

}

然后，知道了像这样的，求众数的方法叫做摩尔投票法（Moore Voting），而且，它是可以求大于等于[n/3]的众数的！

用类似的方法更新两个房间里的数，（可能会有两个众数，也可能只有一个），然后验证两个待选众数是否正确。

代码

public:

    vector<int> majorityElement(vector<int>& nums) {

        int cnt1 = , cnt2 = ;

        int a, b;

        for(int n: nums){

            if (cnt1 ==  || n == a){

                cnt1++; a = n;

            }

            else if (cnt2 ==  || n == b){

                cnt2++; b = n;

            }

            else{

                cnt1--; cnt2--;

            }

        }

        cnt1 = cnt2 = ;

        for(int n: nums){

            if (n == a)   cnt1++;

            else if (n == b) cnt2++;

        }

        vector<int> result;

        if (cnt1 > nums.size()/)   result.push_back(a);

        if (cnt2 > nums.size()/)   result.push_back(b);

        return result;

    }

};

UPD：

在F大爷的博客上还看到了一些神奇的东西。

链接

题意

给定一个长度为n的数列，每个数都是1-n以内。

m次询问，每次询问一个区间，再给定s和k个下标。

如果区间内有一个数出现超过区间长度一半，答案是那个数，否则答案是s，然后把k个下标的位置的数字改成这次的答案。

求每一次的答案和最后整个数列的答案。 n,m<=500000,∑k <=1000000

做法

求众数的做法满足区间加法，所以可以用线段树来维护，每次从区间中找到那个数字。

而我们不能保证最后的数一定出现了超过一半次，

我们可以对每个数开一个平衡树来记录它所出现的位置集合，修改操作也直接在平衡树上进行。

%%%%FallDream！！！！

来自PaperCloud的博客，未经允许，请勿转载，TKS！

redBag