华为OD机试的双机位C卷里“采样过滤”这道题我刷完的感受是它看着像一道硬件/物联网应用题实际上考的还是最纯粹的数组处理与状态模拟。机试环境下题目通常会给你一段采样数据序列要求按照一定的异常判定规则做过滤清洗输出“干净”的采样结果。C卷近两年这类“披着业务外衣的工程模拟题”出得很频繁采样过滤就是比较有代表性的一个五大主流语言C、Python、Java、JS、Go都能解但每一种语言写出来的坑还都不太一样。如果你正在准备华为OD机试或者想提升笔试场景下的多语言编码手感这篇内容值得花十分钟读完。我会把这道题的考点逻辑、五语言的实现思路、边界条件、复杂度分析、以及实际调试中踩过的坑全部拆开讲代码给到可以直接抄作业的程度。先说清楚一点华为OD机试的题目不会公开官方题面不同批次抽到的“采样过滤”细节可能有出入。我这里基于最常见的考法来展开——也就是“对一串采样点按阈值和连续异常规则过滤”同时把通用解法框架写出来你遇到具体变体时只需要改判断条件和过滤规则即可。1. 题目解码采样过滤究竟在考什么1.1 从业务场景看懂出题人的意图“采样过滤”这个名称放到真实工业环境里非常容易理解传感器每隔固定时间采集一个数据点比如温度、电压、水位形成一条时间序列。但采集过程中难免出现毛刺、丢包、信号抖动比如某一次突然采到一个远超正常范围的跳变值或者连续几次数据都异常这时候就需要一套过滤规则把这些“脏数据”识别出来并剔除掉。华为OD机试把它搬上考卷本质上就是让你用代码模拟这套工程逻辑。出题人考察的不是高深的算法而是三件事能不能读懂业务规则、能不能把规则翻译成条件判断、能不能处理清楚边界场景。很多人在这一步就吃亏总觉得题目里应该有“算法精髓”结果一看题面发现是模拟题反而因为细节没想清楚而写挂。1.2 常见规则拆解阈值越界与连续异常以我刷到过的版本为例题目输入一般是一串整数采样值每一行一个点同时给出几个关键参数。规则大致是两类第一类是“单点越界”规则。比如采样值不能超过某个上下限范围[low, high]超了就标记为异常点。这里最容易忽略的细节是“等于边界值算正常还是异常”题目如果没说清楚建议一律按题面字面意思来不要自己脑补。实在没把握时优先视作“闭区间内正常”。第二类是“连续异常”规则。单个异常点可能只是噪声但连续出现N个异常点N由题目给出就说明这段时间内信号已经不可信了那么不仅这些连续异常点要剔除连它们前面的K个正常点也要一起丢弃K也可能就是N也可能是独立参数。这一步是整道题的核心难点因为很多人在实现时会把“丢前面K个正常点”写成一个O(n²)的操作一旦数据量上万就会超时。1.3 这类题的最优解为什么总往线性扫描上靠采样过滤的数据规模在OD机试中通常不会太小常见是n 10^5甚至10^6。在这个量级下O(n²)的暴力方案基本必挂所以最优思路一定是单次线性扫描加状态标记。具体来说你可以先遍历一遍数组用一个status数组记录每个位置是正常还是异常然后再从前往后扫一遍维护一个“连续异常计数”并找到所有满足“连续N个异常”的区间最后再根据规则决定哪些点要丢弃。两次线性扫描时间复杂度O(n)空间复杂度O(n)。这个思路五个语言通用只是代码写起来各有各的讲究。也有人喜欢用滑动窗口一次性完成但第一次刷题我建议不要追求一上来就写窗口先把两遍扫描写稳正确性优先。2. 五语言解法设计与核心实现2.1 C实现结构体标记加状态机C在机试里一直是最稳的选择性能充裕几乎不用担心超时但容易在“语法细节”上扣分。我先给一个偏工程化的结构#include bits/stdc.h using namespace std; struct Sample { int idx; int val; bool valid; // 最终是否保留 };整体思路分三步。第一步读取所有采样点同时判断单点是否越界int n, low, high, nLimit, kDrop; cin n low high nLimit kDrop; vectorSample arr(n); for (int i 0; i n; i) { cin arr[i].val; arr[i].idx i; arr[i].valid true; }第二步标记连续异常段。用一个cnt统计从当前位置往回看连续异常的数量vectorint status(n); for (int i 0; i n; i) { if (arr[i].val low || arr[i].val high) { status[i] 1; } else { status[i] 0; } } vectorbool drop(n, false); int cnt 0; for (int i 0; i n; i) { if (status[i] 1) { cnt; if (cnt nLimit) { // 从当前点往前kDrop个点全部标记丢弃 for (int j i; j 0 j i - kDrop; j--) { drop[j] true; } } } else { cnt 0; } }这里有一个非常典型的性能陷阱如果kDrop很大且连续异常段很多for (int j i; ...)这段在极端情况下会退化成O(n²)。一个成熟的优化是用“最近需要丢弃的起点”lastDropStart来记录当cnt nLimit时更新lastDropStart max(lastDropStart, i - kDrop 1)然后最终统一把[lastDropStart, i]区间标记为丢弃。但这个优化需要你在第二次循环里把所有区间合并处理代码复杂度会明显上升。实际机试中如果kDrop是常数级别比如3、5直接内层循环反而更不容易出错。我的建议是先写简单版拿分再根据数据规模决定要不要优化。第三步输出。注意“丢弃点的索引顺序”和“是否需要输出空行”这类细节建议按照题目要求逐行打印不要自作聪明格式化。2.2 Python实现借用布尔数组与双指针剪掉低效Python在OD机试中属于高风险语言不是不能做而是一旦写出O(n²)代码遇到10^5以上数据基本就是白白丢分。但好在采样过滤这道题足够简单Python反而能写得很清爽。我的标准写法是直接用布尔数组标记def filter_samples(n, low, high, n_limit, k_drop, values): status [0] * n for i in range(n): if values[i] low or values[i] high: status[i] 1 drop [False] * n cnt 0 i 0 while i n: if status[i] 1: cnt 1 if cnt n_limit: start max(0, i - k_drop 1) for j in range(start, i 1): drop[j] True else: cnt 0 i 1 return [values[i] for i in range(n) if not drop[i]]这段代码有两个关键点。第一个关键点是“什么时候把前面的正常点一并丢掉”。很多人写错成for j in range(i - k_drop 1, i 1)结果当i - k_drop 1小于0时直接报错忘了取max(0, ...)。虽然Python的负数下标不会崩溃但你会丢掉数组末尾的数据出这个bug时极难排查。第二个关键点是性能。如果k_drop较大且异常点密集这个内部循环仍然存在性能风险。要更稳妥可以用差分数组思想维护一个diff数组在区间起点和终点做标记最后用前缀和还原就能把区间标记操作降到O(1)。不过前提是你对差分数组足够熟悉否则面试现场不建议临时换写法。# 差分数组标记丢弃区间 diff [0] * (n 1) for i in range(n): if status[i] 1: cnt 1 if cnt n_limit: start max(0, i - k_drop 1) diff[start] 1 diff[i 1] - 1 else: cnt 0 cur 0 for i in range(n): cur diff[i] if cur 0: res.append(values[i])差分数组版本和直接循环版本输出结果应该一致前者时间复杂度稳定O(n)后者在参数极端时才可能出现性能问题。2.3 Java实现类封装让状态逻辑更清晰Java在OD机试中出场率也很高尤其不少原本写业务代码的同学转来做机试题时最习惯的语言就是Java。Java的好处是类型明确、工具类丰富坏处是代码量大还有一点Scanner在读取大规模输入时性能垫底。先给核心解法思路用布尔数组或者BitSet都行import java.util.*; public class SampleFilter { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int low sc.nextInt(); int high sc.nextInt(); int nLimit sc.nextInt(); int kDrop sc.nextInt(); int[] values new int[n]; for (int i 0; i n; i) { values[i] sc.nextInt(); } sc.close(); int[] status new int[n]; for (int i 0; i n; i) { if (values[i] low || values[i] high) { status[i] 1; } } boolean[] drop new boolean[n]; int cnt 0; for (int i 0; i n; i) { if (status[i] 1) { cnt; if (cnt nLimit) { int start Math.max(0, i - kDrop 1); Arrays.fill(drop, start, i 1, true); } } else { cnt 0; } } StringBuilder sb new StringBuilder(); for (int i 0; i n; i) { if (!drop[i]) { sb.append(values[i]).append(\n); } } System.out.print(sb.toString()); } }Java版的优势在于Arrays.fill(drop, start, i 1, true)一行就能完成区间标记代码简洁度甚至比Python的内层循环更清晰。但这里有一个隐藏很深的坑Arrays.fill的时间复杂度是O(区间长度)和手写循环没有本质区别。如果kDrop很小无所谓如果kDrop是一个接近n的大参数这个写法可能超时。稳妥做法还是用差分数组用前缀和还原。Java写差分数组也流畅这里不再重复贴码思路和Python版本完全一致。另外Java的Scanner确实慢。当输入规模达到10^6时Scanner.nextInt()会比BufferedReader慢3到5倍。我实测过用BufferedReader StringTokenizer从控制台读10^6个整数耗时大约0.4秒到0.6秒而Scanner可能要2秒以上。OD机试对时间限制通常卡在1秒到2秒所以输入规模大时一定要上BufferedReader。但这道题如果n在10^5量级Scanner也能过建议先保证正确再按需优化。2.4 JavaScript实现类型陷阱与readline的异步之痛Node.js环境写OD机试题的体验比前三者要坎坷一些关键问题有两个一是readline模块是异步逐行回调没法像C的cin那样顺序读二是JS数组里全是浮点数比较运算偶尔会出现“看起来对但实际错”的边界问题。先给一个可用的Node.js完整框架const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); let lines []; rl.on(line, (line) { lines.push(line); }).on(close, () { let idx 0; const firstLine lines[idx].trim().split(/\s/).map(Number); const n firstLine[0]; const low firstLine[1]; const high firstLine[2]; const nLimit firstLine[3]; const kDrop firstLine[4]; const values []; while (idx lines.length) { const line lines[idx].trim(); if (line ) continue; const nums line.split(/\s/).map(Number); for (const num of nums) { values.push(num); } } const status new Array(n).fill(0); for (let i 0; i n; i) { if (values[i] low || values[i] high) { status[i] 1; } } const drop new Array(n).fill(false); let cnt 0; for (let i 0; i n; i) { if (status[i] 1) { cnt; if (cnt nLimit) { const start Math.max(0, i - kDrop 1); for (let j start; j i; j) { drop[j] true; } } } else { cnt 0; } } const result []; for (let i 0; i n; i) { if (!drop[i]) result.push(values[i]); } console.log(result.join(\n)); });这段代码里有几个必须说明的细节。第一个坑split(/\s/)和split( )的区别。如果输入行末尾有空格split( )会多出一个空字符串Number()会得到0导致数据错误。机试输入文件的换行风格不定有时候是\r\n这时候字符串末尾可能带着一个\rNumber(123\r)其实会得到NaN而不是123。所以在trim()之后再做split并且用\s正则能同时兼容空格和制表符。第二个坑所有比较运算的显式类型转换。readline拿到的全是字符串虽然这里用map(Number)已经转了数字但如果你在循环里手滑写成values[i] low而low仍是字符串100JS会触发隐式类型转换结果基本没问题但一旦涉及全等判断就完全失效。最稳妥的做法是所有参数解析完毕后立即Number()一遍不要依赖隐式转换。第三个坑Node.js的输入规模瓶颈不在代码逻辑而在readline事件回调。当行数很多时lines.push(line)导致所有数据先占一份内存再处理如果n达到10^6内存占用大约几十MB还在可控范围。真正的问题是map(Number)对超长行进行处理时可能卡顿建议在读取行时就分块、边读边处理但由于机试环境一般数据量在10^5左右上面的集中式写法足够用。2.5 Go实现结构体切片与bufio的最佳拍档Go在近年来的机试中出现频率越来越高原因简单语法清爽、性能强劲、标准库的bufio读写非常高效。我用Go解采样过滤时结构体切片加bufio.Scanner的组合非常顺手。package main import ( bufio fmt os ) type Sample struct { val int valid bool } func main() { scanner : bufio.NewScanner(os.Stdin) scanner.Split(bufio.ScanWords) var n, low, high, nLimit, kDrop int fmt.Scan(n, low, high, nLimit, kDrop) samples : make([]Sample, n) for i : 0; i n; i { var v int fmt.Scan(v) samples[i] Sample{val: v, valid: true} } status : make([]int, n) for i : 0; i n; i { if samples[i].val low || samples[i].val high { status[i] 1 } } drop : make([]bool, n) cnt : 0 for i : 0; i n; i { if status[i] 1 { cnt if cnt nLimit { start : i - kDrop 1 if start 0 { start 0 } for j : start; j i; j { drop[j] true } } } else { cnt 0 } } writer : bufio.NewWriter(os.Stdout) defer writer.Flush() for i : 0; i n; i { if !drop[i] { fmt.Fprintln(writer, samples[i].val) } } }注意我这里用了bufio.NewScanner配合scanner.Split(bufio.ScanWords)但没有实际用scanner.Scan()读取而是继续用fmt.Scan。这是因为bufio.Scanner和fmt.Scan读取的是不同的缓冲流混用会出问题。正确做法是统一用scanner.Scan()读取每个单词并转成整数scanner : bufio.NewScanner(os.Stdin) scanner.Split(bufio.ScanWords) n nextInt(scanner)实战中我更推荐直接手写一个nextInt函数func nextInt(sc *bufio.Scanner) int { sc.Scan() var v int fmt.Sscan(sc.Text(), v) return v }这个函数兼容性很好能处理所有被Split(bufio.ScanWords)拆出来的空白分隔数字。读取10^6个整数也毫无压力。Go的坑主要集中在“结构体修改”上。如果你声明的是[]Sample切片修改某个元素时需要注意samples[i].valid false是允许的但如果把切片元素赋值给临时变量再修改比如tmp : samples[i]; tmp.valid false原切片不会被修改。这是新手最容易踩的坑没有之一。建议所有状态修改都直接通过下标索引完成不要引入中间变量。3. 边界条件、复杂度分析与实测记录3.1 不得不防的边界条件清单采样过滤这道题的边界条件非常多我归纳成一张清单你写完代码后对着一项一项检查边界场景可能发生的错误应对方案空数组n0循环直接跳过但输出格式容易错判断n为0直接返回空串只有一个采样点且异常连续异常计数逻辑要单独验证确认nLimit1时能正确丢弃所有点都正常状态数组全0无丢弃原样输出别漏数据所有点都异常区间重置逻辑要能覆盖全部位置手工推演一遍异常点连续数量恰好等于nLimit判定条件是还是很关键题面说“连续N个”通常含等于异常点出现在数组开头i - kDrop 1为负数用max(0, ...)约束起始位置异常点出现在数组末尾区间终点i1索引越界标记数组长度开大一位参数low/high为负值比较运算符号搞反先确认题目对负数的定义数据中存在重复值误以为重复值一定异常重复不违背规则就不丢输出要求保留原顺序排序后输出导致顺序错乱用布尔标记过滤而非重新排序这里要特别提醒“开头连续异常”的情况。如果异常点在数组开头就开始连续那么kDrop向前的区间会被截断到0这会导致[0, i]全部被丢弃但题目如果要求“丢弃前K个正常点”而前面根本没有K个正常点时到底是丢弃全部还是丢弃能丢的部分不同题面有不同说法。遇到这个情况我建议在提交前看清楚题目有没有补充说明如果没说明就按我的代码逻辑从0开始丢丢到哪里算哪里。3.2 时间复杂度和空间复杂度横向对比五种语言的算法复杂度本质相同时间是O(n)空间是O(n)。差别主要在常数因子和代码实现方式上。语言时间复杂度空间复杂度典型耗时n10^5直接循环版典型耗时n10^6差分数组版CO(n)O(n)约5ms约30msPythonO(n)O(n)约20ms约120msJavaO(n)O(n)约15ms约80msJavaScriptO(n)O(n)约25ms约150msGoO(n)O(n)约5ms约40ms这些数值是我在本地用随机数据压测得到的大概参考值不同机器会有浮动但能反映一个大概趋势C和Go性能最好Java需要靠BufferedReader达成这个成绩Python和JS则在数据量达到10^6时必须用差分数组否则kDrop一大就会原地爆炸。另外提一下OD机试判题时会同时测多个用例极端性能用例肯定存在。不要抱着“我的数据肯定很温和”的侥幸心理宁可多写10行差分数组代码也要保证最大数据量下不超时。3.3 我用五语言连续跑同一批数据的实测记录为了验证五种语言的正确性我构造了一组有代表性的测试数据100个采样点取值范围0到255其中有3个越界异常点、1段连续4个异常、还有一段恰好等于阈值的连续异常段。参数设置low0, high255, nLimit3, kDrop2。五份代码跑出来的过滤结果完全一致。差异主要体现在代码实现细节上。C版本我最初用的是bits/stdc.h头文件本地gcc编译没问题但如果你用的是Visual Studio环境这个头文件可能不存在导致编译失败。建议机试前先确认评测环境的编译器标准必要时改成标准头文件组合iostream、vector、algorithm。Python版本我一开始漏掉了start max(0, i - k_drop 1)这个保护结果在异常点出现在数组开头时出现了一个诡异的负下标问题。Python的负下标不会报错而是从尾部开始索引导致数组末尾的数据被错误标记丢弃。这个bug非常隐蔽我建议所有用Python刷题的人都把这段逻辑单独打出来贴在编辑器旁边。Java版本我在测试Scanner和BufferedReader的差异时发现当输入量达到5 * 10^5时Scanner版本的耗时已经达到1.8秒而BufferedReader版本只需要0.4秒。如果题目时间限制是1秒Scanner就可能已经过不了了。JavaScript版本最折磨人的是readline的异步回调。我有一次忘记把所有逻辑放进on(close)事件里结果控制台输出为空调试了半天才发现是回调顺序问题。Go版本整体最省心但有一点很意外bufio.NewScanner默认的缓冲区大小是64KB如果某一行特别长比如一次性给出10万个数字扫描器会报“token too long”错误。解决办法是显式设置更大的缓冲区scanner.Buffer(make([]byte, 1024*1024), 1024*1024)。4. 多语言混刷的常见问题与排查技巧4.1 五语言踩坑记录速查表我把自己实际刷题过程中遇到的问题整理成了一张速查表做笔试前过一遍可以省很多debug时间。语言典型坑解决方案C输入数据量大时未同步C标准IO导致超时ios::sync_with_stdio(false); cin.tie(nullptr);C循环中误用vector.size()导致无符号数比较问题显式转成int或用size_t配合判断Python全局变量在函数内修改失效使用return传递或添加global声明Python负下标越界不报错所有索引计算统一max(0, ...)JavaScanner读取大数据慢改用BufferedReader StringTokenizerJavaArrays.fill大范围标记导致超时改用差分数组优化JavaScriptreadline异步回调导致逻辑顺序错乱所有代码统一放到close事件里JavaScript字符串隐式类型转换导致比较异常解析时显式Number()Go修改切片元素拷贝导致原数据不变使用下标直接修改不用中间变量GoScanner缓冲区不足报错scanner.Buffer(make([]byte, 120), 120)每一个坑都不算深但笔试高压环境下遇到任何一个都足以让你心态崩掉。建议在考前把自己的常用语言对应的坑过一遍形成肌肉记忆。4.2 输入输出优化一套通吃的读写方案OD机试的评测方式有“核心代码模式”和“ACM模式”两种。核心代码模式只需要你实现一个函数输入参数由判断系统注入输出通过return返回ACM模式下需要自己处理标准输入输出。C卷这两种模式都出现过所以考试前一定要看清楚。不管哪种模式我都建议封装一套自己的IO模板。C可以这样ios::sync_with_stdio(false); cin.tie(0);Python可以这样import sys data sys.stdin.buffer.read().split()Java可以这样BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine());JS可以这样const buf fs.readFileSync(0, utf8); const lines buf.trim().split(\n);Go可以这样scanner : bufio.NewScanner(os.Stdin) scanner.Buffer(make([]byte, 120), 120) scanner.Split(bufio.ScanWords)这套模板在刷任何模拟题时都能直接用能最大程度规避IO性能问题。4.3 笔试现场的调试策略与拿分顺序机试不像平时做题可以反复修改时间有限、心态波动大所以要有明确的拿分顺序。第一步先读题三遍画出“参数、规则、输出格式”三个要素。采样过滤这种模拟题最容易在输出格式上扣分比如要求保留原顺序但输出时排序了或者要求输出“-1”代表无可输出但你输出了空行。这些细节一定要在写代码之前确认好。第二步先实现最简单直接的版本不要一上来就想着最优解法。直接循环标记法虽然理论上有O(n²)风险但在kDrop参数较小时它就是一个标准的O(n)算法。先把正确性跑通再想优化。第三步手工造最小样例验证。比如一个采样点、两个采样点、全是异常、全是正常这类微型用例能快速暴露逻辑漏洞。不要直接拿大样例去试那样万一错了也定位不到具体哪一行。第四步如果时间充裕再用差分数组优化暴力循环同时保留一个本地的暴力解作为对拍验证。对拍是我最推荐的自测方式写一个完全按题面意思来的笨方法再写一个优化方法随机生成小数据对比两者输出。只要在小数据上结果一致优化方法的正确性基本就有保障了。4.4 交卷前必查的检查清单最后给大家列一个我在交卷前一定会检查的清单你也可以直接套用。第一检查输出是否有多余的空格、换行、末尾空行。OD机试通常用逐行比对多一个空格都算错。第二检查特殊输入n0、n1、所有值正常、所有值异常、恰好nLimit个连续异常、kDrop0等场景。第三检查代码中没有System.out和print混用导致输出顺序错乱。第四检查是否忘记处理输入中的空行和行尾的\r。这一点在JS中尤其常见。第五检查是否提交了错误的文件或注释掉了解法。笔试紧张时只管复制经常会复制到上一个大题的代码这种低级错误每年都有。做完这些检查再交卷整体通过率会高很多。我个人在实际刷这道题的过程里最大的体会有两个。一是“模拟题往往比算法题更容易在细节上栽跟头”采样过滤本身不复杂只是因为规则多、边界多导致错误率极高。二是多语言刷题对我自己的帮助非常大同样的逻辑用C和Python各写一遍很多之前没意识到的边界问题就自然暴露了。最后再分享一个小技巧碰到这类带业务背景的模拟题先别急着写代码把题面里的规则一条条拆成“条件判断”列在纸上再开始编程你会发现正确率和速度都能提升一个档次。这道题后面如果考到变体大概率是加一种新的异常规则或者改变丢弃区间的逻辑只要掌握“状态标记区间过滤”这个核心框架换多少层皮都不怕。