P2681 众数 题解报告

· · 个人记录

众数

题干很简明，如果你不知道众数是什么，请戳 这里。

数据范围并不大，可以直接暴力，统计众数。

此处介绍三种方法

一、map

map 是 STL 中的一种关联式容器，储存 键值对，内部由红黑树实现，自动实现键的排序，常见操作均为对数复杂度。

想进一步了解的可以去看 这个。

理论时间复杂度：O(mn\log n)。

实际用时：80ms

代码：

int n,m,a[inf];
map<int,int>T;
int main()
{
    n=re();m=re();
    for(int i=1;i<=n;i++)
        a[i]=re();
    for(int i=1;i<=m;i++)
    {
        int op=re(),x=re(),y=re();
        if(op)a[x]=y;
        else
        {
            T.clear();
            int sum=0,zs=0;
            for(int j=x;j<=y;j++)
            {
                T[a[j]]++;
                if((sum<T[a[j]])||(sum==T[a[j]]&&zs>a[j]))
                    zs=a[j],sum=T[a[j]];
            }
            wr(zs);putchar('\n');
        }
    }
    return 0;
}

二、unordered_map

上文说过，map 内部自动排序。而 C++11 之后，四个基于 哈希 的无序关联式容器正式纳入 STL，unordered_map 就是其中之一。

至于其他三个，在这

那么就可以去掉一个 log，理论时间复杂度 O(mn)。

但……

实际用时：110ms

这就是人傻常熟大吗

代码：

int n,m,a[inf];
unordered_map<int,int>T;
int main()
{
    n=re();m=re();
    for(int i=1;i<=n;i++)
        a[i]=re();
    for(int i=1;i<=m;i++)
    {
        int op=re(),x=re(),y=re();
        if(op)a[x]=y;
        else
        {
            T.clear();
            int sum=0,zs=0;
            for(int j=x;j<=y;j++)
            {
                T[a[j]]++;
                if((sum<T[a[j]])||(sum==T[a[j]]&&zs>a[j]))
                    zs=a[j],sum=T[a[j]];
            }
            wr(zs);putchar('\n');
        }
    }
    return 0;
}

三、离散化

值域相关的题大多之后，离散化都是基操。

感觉这个博客写的还可以

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

对于需要开桶且值域很大的情况或有负数、浮点数的情况，离散化就派上用处了。

或许这样更简洁：

if( (需要开桶) && (值域很大 || 有负数、浮点数))
{
    使用离散化
}

那么这个题，显然就可以离散化。

理论复杂度：O(n\log n+mn)。

实际用时：40ms

一不小心拱了个最优解

代码：

int n,m,a[inf],T[inf];
int bok[inf<<1],cnt;
int op[inf],x[inf],y[inf];
int main()
{
    n=re();m=re();
    for(int i=1;i<=n;i++)
        a[i]=re(),bok[++cnt]=a[i];
    for(int i=1;i<=m;i++)
    {
        op[i]=re(),x[i]=re(),y[i]=re();
        if(op[i])bok[++cnt]=y[i];
    }
    sort(bok+1,bok+cnt+1);
    int num=unique(bok+1,bok+cnt+1)-bok-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(bok+1,bok+num+1,a[i])-bok;
    for(int i=1;i<=m;i++)
        if(op[i])y[i]=lower_bound(bok+1,bok+num+1,y[i])-bok;
    for(int i=1;i<=m;i++)
    {
        if(op[i])a[x[i]]=y[i];
        else
        {
            memset(T,0,sizeof(T));
            int sum=0,zs=0;
            for(int j=x[i];j<=y[i];j++)
            {
                T[a[j]]++;
                if((sum<T[a[j]])||(sum==T[a[j]]&&zs>bok[a[j]]))
                    zs=bok[a[j]],sum=T[a[j]];
            }
            wr(zs);putchar('\n');
        }
    }
    return 0;
}

值得注意的是，离散化不能只对原数组，对于 flag=1 的 y 也要离散化。

这样的话 bok 数组应该开到 m+n，也就是 2e3。

End.