跳到主要内容

主元素问题

参考资料​

简介​

主元素问题（Majority Element Problem）要求在长度为 nn 的序列中，找出出现次数严格超过 ⌊n/2⌋\lfloor n/2\rfloor 的元素。

离线情形下，排序后第 ⌊n/2⌋+1\lfloor n/2\rfloor+1 个元素一定是主元素，利用 nth_element 可在 O(n)O(n) 时间内求得，无需额外空间。

摩尔投票算法（Boyer–Moore Majority Vote Algorithm）是一种在线算法，核心思想：不断消去一对「候选元素」与「非候选元素」，最终剩余的候选即为主元素。维护当前候选 val\mathit{val} 与计数 cnt\mathit{cnt}，初始 cnt=0\mathit{cnt}=0；对每个新元素，若 cnt=0\mathit{cnt}=0 则更新候选，若等于候选则 cnt+1\mathit{cnt}+1，否则 cnt−1\mathit{cnt}-1。全部扫描后 val\mathit{val} 即为答案。时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。

注意：若序列不保证存在主元素，需再扫描一遍验证 val\mathit{val} 的出现次数是否超过 ⌊n/2⌋\lfloor n/2\rfloor。

实现​

324 Bcpp
#include <bits/stdc++.h>
using namespace std;

const int N=100005;
int a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int val=0,cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(cnt==0)val=a[i];
		if(a[i]==val)cnt++;
		else cnt--;
	}
	cout<<val<<'\n';
	return 0;
}

例题​

洛谷 P2397 yyy loves Maths VI (mode)

一共有 nn 个正整数 aia_i，他让 redbag 找众数。他还特意表示，这个众数出现次数超过了一半。