题目描述

令A[1,n]是一个整数序列，A 中的某一元素 a 在数组 A
中出现的次数多于Ln / 2」，那么 a 称为多数元素。
例如，在序列 1、3、2 、3 、3、4 、3 中，3 是 多数元素。

算法1

(对消)

(证明)

归纳假设：
假设对于任意长度小于等于 k 的数组，对消算法都能正确地找出是否存在主要元素。

归纳步骤：
现在考虑一个长度为 k+1 的数组。根据归纳假设，我们知道对于前 k 个元素，如果存在主要元素 M，
那么在进行两两抵消后，剩下的元素仍然是 M。现在将第 k+1 个元素加入考虑。有以下两种情况：

如果第 k+1 个元素和主要元素相同，那么计数器会加1，仍然保持主要元素的性质。
如果第 k+1 个元素和主要元素不同，那么计数器会减1。如果主要元素 M 的出现次数超过一半，
极端情况如果k为偶数数且对消后，那么即使进行抵消，剩下的部分仍然会包含 M。
若k为奇数，在极端情况下，例如k为7，主要元素个数为4个，此时加入一不同元素后将不构成多数元素，
而其他情况则成立。
因此，无论第 k+1 个元素是什么，对消算法都能正确地找出是否存在主要元素。

时间复杂度 $O(n)$

C++ 代码

#include<iostream>
using namespace std;
const int N=100000;
int a[N],n;

void func()
{
    int cdt=a[0],count=1;
    for(int i=1;i<n;i++)
    {
        if(cdt==a[i]) count++;
        else
        {
            count--;
            if(count==0)
            {
                cdt=a[i];
                count=1;
            }
        }
    }
    count = 0;
    bool f=false ;
    for(int i=0;i<n;i++) 
     if(cdt==a[i])
     {
         count++;
         if(count>n/2) 
         {
             f=true;
             break;
         }
     } 
    if(f) cout<<cdt;
    else cout<<"wu";
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    func();
    return 0;
}