主元素问题

include-blog 2020-03-01 原文

一、什么是主元素

在一个数列中出现次数超过50%的数。
例如：3、3、4、3、2、1、3中主元素就是3.

二、怎么求主元素

现给定一个序列，其中有主元素。

方法一：分别记录每个数出现的次数

用一个数组记录每个数出现的次数，就是类似桶排序的方法，数组中次数超过总数一半的那个数就是要求的主元素。

#include <bits/stdc++.h>
using namespace std;
int ans[10001],n,t;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>t;
        ans[t]++;
    }
    for(int i=0;i<10001;i++)
        if(ans[i]>n/2)
        {
            cout<<i;
            break;
        }
    return 0;
}

时间复杂度与空间复杂度都为O(N+M)。
如果跨度很大，可以离散化一下。

方法二：排序后位置为N/2+1的数

如果一个数列中含有主元素，那么排序后主元素就是位于N/2+1位置的数。
举例1：3、3、4、3、2、1、3 -> 1、2、3、3、3、3、4
举例2：3、3、3、3、5、3、1、0 -> 0、1、3、3、3、3、3、5

#include <bits/stdc++.h>
using namespace std;
int n,a[10001];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[n];
    sort(a,a+n);//C++ STL自带排序函数
    cout<<a[n/2+1-1];//减1是因为这里数组从a[0]开始用
    return 0;
}

当然也可以用其他排序算法。
sort函数的时间复杂度是O(NlogN)，总的复杂度为O(NlogN+N)。

方法三：运用含主元素序列的特性

含主元素序列的特性：在序列中去除两个不同的元素，主元素依然存在。
也就是说：进行多次去掉两个不同元素的操作后，剩下的一个或多个相同的数就是要求的主元素。
举例：3、3、4、3、2、1、3 -> 3、3、2、1、3 -> 3、1、3 -> 3
这里在输入时判断与上一次保存的输入是否相同，如不同则删除两数，这里用栈来实现。

#include<bits/stdc++.h>
using namespace std;
int n,q[10001],top=0,a;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        q[top++]=a;
        if(top!=1&&(q[top-1]!=q[top-2]))
            top-=2;
        
    }
    cout<<q[top-1];
    return 0; 
}

时间复杂度为O(N)。
终极压行版：

#include<stdio.h>
int n,q[10001],top=0,a;
int main()
{
    scanf("%d",&n);
    while(n--)scanf("%d",&a),q[top++]=a,top=(top>1&&(q[top-1]!=q[top-2]))?top-2:top;
    printf("%d",q[top-1]);
}