小欧的数组修改

2026/10/24约 1595 字大约 5 分钟

小欧的数组修改

OPPO 笔试真题 · 2023 秋招 · 移动端岗
判题请到牛客原题提交。

题目描述

小欧拿到了一个数组，她可以修改其中任意一个元素的值（也可以不修改），使得出现次数最多的那个元素次数尽可能多。你能求出这个最多的出现次数吗？

输入格式

第一行输入一个正整数 $n$ ，代表数组的大小。

第二行输入 $n$ 个正整数 $a_i$ ，代表数组的各个元素。

$1\leq n,a_i \leq 10^5$

输出格式

一个正整数，代表小欧操作后出现最多的元素次数。

示例

示例 1

输入：

3
1 2 3

输出：

说明：

将1修改为3，数组变成[3,2,3]，3出现了2次。修改方式并不是唯一的。

示例 2

输入：

1
4

输出：

说明：

由于只有一个数，所以无论是否进行修改，它都只出现了1次。

解题思路

第一步：理解问题本质

数组里每个值都有自己的出现次数，我们只能修改一个元素（也可以不改），
目标是让「出现次数最多的那个值」出现得尽可能多。

因为只动一个位置，所以答案的形式很有限：要么什么都不改，
要么把某个位置改成另一个值。

第二步：暴力解法

最直接的想法是枚举「把哪个位置改成什么值」：位置有 $n$ 种，
改成的值最多有 $n+1$ 种候选，而每种情况都要重新数一遍频次（ $O(n)$ ），
总复杂度 $O(n^3)$ 。 $n=10^5$ 时完全不可行。

而且这个枚举里绝大多数情况是明显没用的 —— 我们要的只是那个最大值。

第三步：先找出上界

设当前出现次数最多的值出现了 $c$ 次。

一次修改最多能让某个值的出现次数增加 1 次：

改成的值如果原本就出现了 $c$ 次，它最多变成 $c+1$ 次；
改成的值如果原本出现次数更少，也不会超过 $c+1$ ；
被改掉的那个位置原本属于某个值，只会让那个值的次数减少。

所以答案一定不超过 $c+1$ 。

第四步：上界能不能取到

若 $c=n$ ：整个数组都是同一个值，把任何一个位置改掉都会让 $c$ 变小，
所以最优是不修改，答案是 $n$ 。
若 $c<n$ ：说明还存在「别的值」，从里面挑一个位置改成出现最多的那个值，
它的次数就从 $c$ 变成 $c+1$ ，上界取到。

两种情况合起来正好是

\min(n,\ c+1)

$c=n$ 时 $\min(n,n+1)=n$ ， $c<n$ 时 $\min(n,c+1)=c+1$ ，
一个式子把两种情形都覆盖了，代码里不需要额外分支。

第五步：怎么求 $c$

用一个哈希表（Python 的 dict）边读边计数，同时维护当前的最大频次。
值域是 $10^5$ ，用数组当桶也可以，但 dict 更省事且不依赖值域。

完整代码实现

import sys


def solve():
    """统计每个值出现的次数，取最大值后加一（不超过 n）"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n = int(data[0])
    best = 0
    cnt = {}
    for token in data[1:1 + n]:
        v = int(token)
        c = cnt.get(v, 0) + 1
        cnt[v] = c
        if c > best:
            best = c
    sys.stdout.write(str(min(n, best + 1)) + "\n")


if __name__ == "__main__":
    solve()

示例推演

示例 1：n = 3，数组是 1 2 3。

值	出现次数
1	1
2	1
3	1

最大频次 $c=1$ ，答案 $=\min(3,\ 1+1)=2$ 。

具体做法：把第一个位置的 1 改成 3，数组变成 [3, 2, 3]，3 出现了 2 次。
也可以把 2 改成 1 得到 [1, 1, 3]，同样得到 2 —— 方案不唯一，但最大值唯一。

示例 2：n = 1，数组是 4。

最大频次 $c=1$ ，答案 $=\min(1,\ 2)=1$ 。
只有一个位置，改与不改都只有 1 个数，所以答案是 1。

再补一个「已经全部相同」的情形：4 7 7 7 7。
此时 $c=4=n$ ，答案 $\min(4,5)=4$ —— 保持不动就是最优。

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力枚举「改哪个位置、改成什么」	$O(n^3)$	$O(n)$	每种情况都要重新统计一遍频次
哈希表计数 + 上界分析	$O(n)$	$O(n)$	推荐，一遍扫描即可

易错点总结

1. 忘记和 $n$ 取最小值

如果数组全部由同一个值组成， $c=n$ ，此时 $c+1=n+1$ 是不可能的。
min(n, c+1) 把这个坑堵住。

2. 误以为可以改多个元素

题目是「修改其中任意一个元素的值」，只能改一个。若能改 $k$ 个，
答案会变成 $\min(n, c+k)$ ，不能照搬。

3. 只改一个元素也可能「改坏了」

例如 7 7 7 7，把其中一个 7 改成 5 之后最大频次降到 3。
所以「可以不修改」这个选项是必须保留的， $c=n$ 的情形正是靠它正确处理。

4. 别忘了 $n=1$

只有一个数时，答案恒为 1（改成什么也还是 1 个数）。

5. 读入方式

第一行是 $n$ ，第二行是 $n$ 个数。用 sys.stdin.buffer.read().split()
一次读完再按下标取，比逐行读更省心；注意跳过第一个 token。

扩展思考

若允许最多修改 $k$ 个元素，答案就是 $\min(n, c+k)$ ：先把别的值改过来，
每次最多 +1。
若不仅要答案还要输出方案，需要额外记录「出现次数最多的值」和
「任意一个不属于它的下标」，改完输出数组即可。
若额外要求「修改之后众数必须唯一」，本题的构造已经满足：
被改成的那个值变成 $c+1$ 次，而其它值最多 $c$ 次，不会与它并列。
这道题体现了一个常用思路：先证明上界，再构造出达到上界的方案。
很多贪心题的答案就藏在这两步里，比枚举所有操作快得多。

相关题目

小欧的数组构造