把序列中大于 k 的数替换为序列最大值,小于 k 的数替换为序列最小值,等于 k 的不变。
给定包含 n 个数字的序列 A = [a₁, a₂, …, aₙ]。请把其中大于 k 的数字都替换为序列的最大值,把小于 k 的数字都替换为序列的最小值,输出替换后的序列。
求最大值求最小值原地替换负数处理
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、k;第二行 n 个整数 |
| 输出 | 替换后的 n 个整数 |
| 数据范围 | 1 ≤ n ≤ 10⁵ |
| 数值范围 | |k|, |aᵢ| ≤ 10⁵,可能为负 |
先算极值:最大值是 2,最小值是 −2。
扫描一遍:max = 2(最后一个元素)
min = −2(第一个元素)
max = 2,min = −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]
按顺序输出,空格分隔
✅ −2 −2 0 2 2
| 原值 | 与 k = 0 比较 | 替换为 | 结果 |
|---|---|---|---|
| −2 | 小于 | min = −2 | −2 |
| −1 | 小于 | min = −2 | −2 |
| 0 | 等于 | 不替换 | 0 |
| 1 | 大于 | max = 2 | 2 |
| 2 | 大于 | max = 2 | 2 |
极值和 k 的大小关系不固定,代码不能做任何假设。
| 情形 | n、k、A | max / 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 | 结果全是最大值 |
| 所有数都等于 k | n=3, k=5, A=[5,5,5] | max=5, min=5 | 全部不替换 | 保持原样 |
第一遍求 max/min,第二遍替换
读入时就顺便更新 max/min,之后再统一替换
| 方案 | 遍历次数 | 清晰度 |
|---|---|---|
| 两遍扫描 | 2 次 | ⭐⭐⭐⭐⭐ |
| 边读边记 | 1.5 次 | ⭐⭐⭐ |
第一行输入 k,第二行输入序列(空格分隔),程序会先求极值再逐个替换。
点按钮开始 →
#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(因为它比所有数都大)。必须用第一个元素初始化。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 0 | −2 −2 0 2 2 | 题面样例 |
1 5 | 7 | 单元素:max = min = 7 |
3 100 | 1 1 1 | k 比所有数都大 → 全是 min |
3 −100 | 3 3 3 | k 比所有数都小 → 全是 max |
3 5 | 5 5 5 | 全部等于 k → 不变 |
4 0 | −3 −3 4 4 | 负数与正数混合,max = 4、min = −3 |
a[0] 初始化。需要保存整个序列以便二次遍历,所以空间是 O(n);n ≤ 10⁵ 时约 400 KB,完全没问题。
✅ 10⁵ 规模下三次遍历约 30 万次操作,轻松通过。
// 求极值的正确初始化方式 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) 控制分隔符 | 所有多元素输出题 |