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

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

他让redbag找众数

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

一共n个数,而且保证有

n<=2000000

而且每个数<2^31-1

第一行一个整数n

第二行n个整数

一行,这个众数

5

2 3 3 3 3

时间限制 1s

空间限制 3.5M(你没看错3.5M)

有人想水过,但我告诉你这空间是不够的

//kkksc03偷偷地说：你随便输出一个数字吧，都有1/2的几率。不过这可是乐多赛，值得不值得你看着办。所以最好想一想正解。

思路

Boyer-Moore majority vote algorithm(摩尔投票算法)是一种线性时间复杂度和常数级空间复杂度的算法，用来查找元素序列中的众数（出现次数超过一半的数）。

算法的基本思想：

摩尔投票法的基本思想很简单，在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。这样不断的删除直到无法再进行投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的一半。如果只存在一种元素，那么这个元素则可能为目标元素。（摘自https://www.jianshu.com/p/c19bb428f57a）

在任何数组中，出现次数超过总数一半的数一定最多只有一个

每次从数组中选出一个元素，并设置一个计数器，如果计数器为0，则假设众数x为当前的元素num；如果不为0，判断假设的众数x是否和当前元素num相等，如果相等，计数器+1，否则，计数器-1。

如果到最后计数器为0，那么众数不存在

因为题目保证众数一定存在，所以不需要判断最后计数器的值，只需要输出留在最后的我们假设的众数x的值，即为改数组中的众数

同理，可以拓展到寻找数组中出现次数超过1/3的数

代码

 1 #include <bits/stdc++.h>

 2 #define ll long long

 3 #define ull unsigned long long

 4 #define ms(a,b) memset(a,b,sizeof(a))

 5 const int inf=0x3f3f3f3f;

 6 const ll INF=0x3f3f3f3f3f3f3f3f;

 7 const int maxn=2e7+10;

 8 const int mod=1e9+7;

 9 const int maxm=1e3+10;

10 using namespace std;

11 int main(int argc, char const *argv[])

12 {

13     ios::sync_with_stdio(false);

14     cin.tie(0);

15     int n;

16     cin>>n;

17     ll x;

18     int res=0;

19     ll ans;

20     int i;

21     for(i=0;i<n;i++)

22     {

23         cin>>x;

24         if(!res)

25             ans=x;

26         if(x==ans)

27             res++;

28         if(x!=ans)

29             res--;

30     }

31     cout<<ans<<endl;

32     return 0;

33 }