考点：哈希

数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：n ≤ 1e5
• 元素值域：a_i ≤ 1e5（注意整数类型选择，避免溢出）
• 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：哈希

本题切入点

统计每种取值的出现次数；把某个元素改成相邻值可使该值计数 +1，因此答案 = max(某值次数, 某值次数 + 另一个被改元素是否为同值或相邻值)。

用哈希表把「查找/计数」的开销降到 O(1) 均摊。

思路框架（哈希 通法 · 非本题专属）

1. 一次遍历，把元素作为 key、出现次数/首次位置作为 value 存进哈希表。
2. 第二次遍历（或边扫边查）拿到需要的信息。
3. 注意哈希无序：需要按原顺序输出时要额外记录顺序。

实现要点：Python 用 dict / collections.Counter / defaultdict；C++ 用 unordered_map。

复杂度：时间 O(n) 均摊 ｜ 空间 O(n)

该范式的通法易错点

• 遍历哈希表时依赖了不存在的顺序。
• 多次查询时每次都重新统计。

对照本题

• 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 元素值域最大到 1e5 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3 / 1 2 3 → 输出 2

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

样例 2：输入 1 / 4 → 输出 1

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