求众数（主元素问题）

2020-10-12 算法主元素问题

一、问题

在长度为 $n$ 的数列 $a$ 中找到出现次数超过一半的数（保证数列中只有一个这样的数）。

二、解法

1.最朴素的方法

开一个桶存储每个数出现的次数，枚举每个数，找出现次数超过一半的数就可以了。

代码：略（桶应该都会吧）。

时间复杂度： $O(max\{a_i\})$ ，如果 $a_i$ 特别大就肯定超时，所以要想别的办法。

2.排序

先对 $a_i$ 排序，之后从 $1$ 到 $n$ 枚举每个数，计算它出现的次数，取次数超过一半的数。

代码：

#include <cstdio>
#include <algorithm>
int n,a[MAXN];//MAXN为n的最大值
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    std::sort(a+1,a+1+n);
    int s=1,ans=a[1];
    for(int i=2;i<=n;i++){
        if(a[i]==a[i-1]) ++s;
        else s=1;
        if(s>n/2) ans=a[i];
    }
    if(s>n/2) ans=a[n];
    /*
    最后可能有没统计完的。
    比如说1 3 5 5 5，5是众数却没有在循环里判断到，所以在循环外再判断一次。
    */
    printf("%d\n",ans);
    return 0;
}

时间复杂度： $O(nlogn)$ ，已经很优了。但是还有更优的解法。

3.摩尔投票法

摩尔投票法的基本思想就是对于 $n$ 个数，如果其中有且仅有一个是众数，那么去掉两个数后，剩下的 $n-2$ 个数中的众数与原来的相同。

这个思想很难理解，但可以这么想：

设 $n$ 个数中，众数出现次数是 $x$ ，则有三种可能：

去掉的两个数都不是众数：

显然剩下的 $n-2$ 个数的众数与原来相同，因为去掉的两个数不是众数。
去掉的两个数一个是众数，一个不是：

去掉了一个众数，剩下来的 $n-2$ 个数中，众数的个数 $s \ge \frac{n}{2}$ 。

则 $2s \ge n$ ， $2s$ 一定大于 $n-2$ ，即 $s>\frac{n-2}{2}$ ，剩下的 $n-2$ 个数的众数与原来相同。
去掉的两个数都是众数：

设去掉后众数出现次数是 $s$ ，总共有 $n-2$ 个数。

$\because s > \frac{n-2}{2}$

$\therefore 2s+2>n$

$\therefore s+1 > \frac{n}{2}$

$\because x>s$ （如果 $x=s$ 则压根没删）

$\therefore x \ge s+1$

$\therefore x \ge s+1 > \frac{n}{2}$ ，去掉后剩下的 $n-2$ 个数的众数与原来相同。

所以只要每次从数列中删掉两个数，众数都不会变。因此可以设第一个元素为众数，再设一个计数器 $s$ ，初始值为 $1$ 。从第二个数开始，如果当前数与众数相同，计数器加 $1$ ，否则减 $1$ 。如果此时 $s=0$ ，则根据刚刚的推导过程，可以将此时的数当作众数。最后求的就是众数。

这种做法有个前提条件是数列中有且只有一个是众数。如果没有这个说明，则最后需要检验一下出现次数是否大于 $\frac{n}{2}$ 。

代码：

#include <cstdio>
int n,a[MAXN],Main,s=1;//main为求的众数
bool check(int x){
    int s=0;
    for(int i=1;i<=n;i++) if(a[i]==x) ++s;
    return s>n/2;
}
int main(){
	scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	Main=a[1];
	for(int i=2;i<=n;i++){
		if(Main==a[i]) ++s;
		else --s;
		if(!s) Main=a[i],s=1;//这句要后做
	}
    if(check(Main)) printf("%d\n",Main);
    else printf("-1\n");
	return 0;
}

三、相关题目

[洛谷P2397]yyy loves Maths VI (mode)

主元素问题的模板题。注意内存限制，不能开数组。