GESP 题解库 / 3 级题解 / [GESP202412 三级] 数字替换 · 第 11 / 28 题
GESP202412 三级 · B4066 · 入门

数字替换

把序列中大于 k 的数替换为序列最大值,小于 k 的数替换为序列最小值,等于 k 的不变。

📊
n ≤ 10⁵
数据规模
🔢
|aᵢ| ≤ 10⁵
数值范围
⚡
O(n)
时间复杂度
🎯
找极值 + 遍历替换
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定包含 n 个数字的序列 A = [a₁, a₂, …, aₙ]。请把其中大于 k 的数字都替换为序列的最大值,把小于 k 的数字都替换为序列的最小值,输出替换后的序列。

💡
人话翻译:先把原序列的最大和最小找出来(这一步必须在替换之前完成),然后逐个判断:比 k 大就换成最大值,比 k 小就换成最小值,等于 k 的原样不动。

🔍 关键词提取

求最大值求最小值原地替换负数处理

已知条件

项目说明
输入第一行 n、k;第二行 n 个整数
输出替换后的 n 个整数
数据范围1 ≤ n ≤ 10⁵
数值范围|k|, |aᵢ| ≤ 10⁵,可能为负

需要解决的问题

02
思维导图
整理解题思路的全貌
🔁 先求极值,再逐个替换
📥 读入
n 和 k
n 个整数存进数组
注意可能有负数
用 int 就够
📏 先求极值
遍历一遍求 max
遍历一遍求 min
必须在替换前算完
这是本题关键顺序
🔁 逐个替换
aᵢ > k → 改成 max
aᵢ < k → 改成 min
aᵢ == k → 不动
边判断边输出也行
⚠️ 注意点
极值与 k 的大小关系不定
输出用空格分隔
行末可以有空格但最好没有
n 很大要注意效率
03
样例手算推导
样例 5 个数字逐个判断

🧮 样例:n = 5,k = 0,A = [−2, −1, 0, 1, 2]

先算极值:最大值是 2,最小值是 −2。

1
确定极值

扫描一遍:max = 2(最后一个元素)

min = −2(第一个元素)

max = 2,min = −2

2
逐个判断

a₁ = −2 < 0 → 替换为 min = −2(恰好不变)

a₂ = −1 < 0 → 替换为 min = −2

a₃ = 0 == k → 保持不变,仍为 0

a₄ = 1 > 0 → 替换为 max = 2

a₅ = 2 > 0 → 替换为 max = 2(恰好不变)

得到 [−2, −2, 0, 2, 2]

3
输出

按顺序输出,空格分隔

✅ −2 −2 0 2 2

📊 逐个判断表

原值与 k = 0 比较替换为结果
−2小于min = −2−2
−1小于min = −2−2
0等于不替换0
1大于max = 22
2大于max = 22
🔑
为什么"先求极值"不能省?如果一边替换一边更新极值,被改过的元素会影响 max/min 的计算,结果就错了。正确顺序是:先完整扫一遍求极值,再扫第二遍替换。

🧮 再看两个边界情形

极值和 k 的大小关系不固定,代码不能做任何假设。

情形n、k、Amax / min结果说明
k 比所有数都大n=3, k=100, A=[1,2,3]max=3, min=1全都 < k → 全变 1结果全是最小值
k 比所有数都小n=3, k=−100, A=[1,2,3]max=3, min=1全都 > k → 全变 3结果全是最大值
所有数都等于 kn=3, k=5, A=[5,5,5]max=5, min=5全部不替换保持原样
⚠️
不要假设 max ≥ k ≥ min:题面没有这个保证。k 完全可能比所有元素都大或都小,这时结果会变成"全是同一个值"。上面的表就是这几种边界。
04
解法对比
两遍扫描 vs 边读边记

⚔️ 解法对比

🟢 两遍扫描(推荐) 推荐

第一遍求 max/min,第二遍替换

  • 时间 O(n)
  • 逻辑最清晰
  • 不会受替换影响
  • 空间 O(n) 存数组
💡
为什么推荐:把"求极值"和"替换"两件事彻底分开,顺序上的正确性一目了然,不会写出隐蔽的 bug。

🟠 边读入边记极值

读入时就顺便更新 max/min,之后再统一替换

  • 本质仍是两遍(读 + 替换)
  • 少一次遍历但代码稍绕
  • 需要保存整个数组
  • 收益很小
⚠️
注意:这种写法的前提是"读入阶段不做任何替换",否则极值会被污染。容易写着写着就混在一起了。

📈 性能对比

方案遍历次数清晰度
两遍扫描2 次⭐⭐⭐⭐⭐
边读边记1.5 次⭐⭐⭐
05
算法流程图
求极值 → 判断替换 → 输出
开始读入 n、k 和数组 A第一遍扫描:求出 max 和 mini 从 0 到 n−1aᵢ 与 k 的关系?aᵢ > k → 变成 maxaᵢ < k → 变成 min等于 k → 保持不变原样输出n 个元素都处理完了吗?按空格输出结果序列结束还有元素 → 继续判断
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔁 数字替换模拟器

第一行输入 k,第二行输入序列(空格分隔),程序会先求极值再逐个替换。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int a[MAXN];

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    // 第一遍:求出原序列的最大值和最小值(必须在替换前完成)
    int mx = a[0], mn = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] > mx) mx = a[i];
        if (a[i] < mn) mn = a[i];
    }

    // 第二遍:按规则替换
    for (int i = 0; i < n; i++) {
        if (a[i] > k)      a[i] = mx;
        else if (a[i] < k) a[i] = mn;
        // 等于 k 时什么都不做
    }

    for (int i = 0; i < n; i++) {
        if (i) printf(" ");
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}
🔑
输出技巧:用 if (i) printf(" ") 控制空格,可以避免"行末多一个空格"。虽然多数评测会忽略行末空格,但严格比对时会判错,养成不留行末空格的习惯。

📖 关键几行怎么看

代码作用为什么这样写
int mx = a[0], mn = a[0];初始化极值用第一个元素初始化,避免设成 0 在负数场景下出错
for (i = 1; ...)求极值从第 2 个开始即可
a[i] > k / a[i] < k判断替换两个分支都用严格比较,等于 k 自然落到"不处理"
if (i) printf(" ");控制分隔符第一个元素前面不输出空格
⚠️
初始化极值的陷阱:如果写成 int mx = 0, mn = 0;,当所有数字都是负数时,max 会错误地保持 0(因为它比所有数都大)。必须用第一个元素初始化。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5 0
−2 −1 0 1 2
−2 −2 0 2 2题面样例
1 5
7
7单元素:max = min = 7
3 100
1 2 3
1 1 1k 比所有数都大 → 全是 min
3 −100
1 2 3
3 3 3k 比所有数都小 → 全是 max
3 5
5 5 5
5 5 5全部等于 k → 不变
4 0
−3 −1 2 4
−3 −3 4 4负数与正数混合,max = 4、min = −3
✅
自查清单:① 极值用第一个元素初始化了吗?② 求极值在替换之前吗?③ 等于 k 的分支处理了吗?④ 行末有没有多余空格?

🚨 易错点清单

⚠️
用 0 初始化极值:全是负数时 max 会错成 0。必须用 a[0] 初始化。
⚠️
先替换再求极值:顺序反了,极值会被替换后的值污染。
⚠️
把"等于 k"也一起处理了:题目只说大于和小于,等于 k 的必须保持原值。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
n 最大
10⁵
遍历次数
2 ~ 3 次

时间怎么算的?

空间都用在哪?

需要保存整个序列以便二次遍历,所以空间是 O(n);n ≤ 10⁵ 时约 400 KB,完全没问题。

✅ 10⁵ 规模下三次遍历约 30 万次操作,轻松通过。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 求极值的正确初始化方式
int mx = a[0], mn = a[0];          // 用第一个元素初始化(最稳)
// 不要写成 int mx = 0, mn = 0;  ——负数场景会错

// 也可以用算法库(要求数组非空)
int mx = *max_element(a, a + n);
int mn = *min_element(a, a + n);

// 输出时不带行末空格的标准写法
for (int i = 0; i < n; i++) {
    if (i) printf(" ");
    printf("%d", a[i]);
}
printf("\n");

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
求极值一趟扫描记录最大最小统计类、范围判断类题目
两阶段处理先收集信息,再统一修改需要"原始数据"的替换/映射题
无行末空格输出用 if (i) 控制分隔符所有多元素输出题
🌟
思考题:如果把规则改成"大于 k 的替换为大于 k 的元素中的最小值",代码要增加什么?(提示:需要在第一遍扫描时同时统计"大于 k 的元素"的极值,而不能先替换再算。)