写在前面

本次给大家带来2026年8月8日OPPO笔试题的2道题，本场机考题目可在咱们平台上在线刷题。

第一题：先记录排列中每个数字所在的位置，再按  的顺序比较相邻数字的位置大小，统计向左和向右的次数即可；

第二题：先用训练集均值补全缺失值并标准化，再用训练集训练 ，以样本的重建平方误差作为异常分数，并用训练误差的  分位数作为阈值判断测试样本是否异常。

塔子哥的配套刷题网站:codefun2000.com

第1题-序号巡检轨迹

题目内容

一条线性巡检带上依次设置了  个检测点，每个检测点被分配了一个唯一的巡检序号。巡检设备需要严格按照序号从小到大的次序依次访问这些检测点，并记录移动方向。

给定一个长度为  的排列 ，其中  的每个整数都恰好出现一次。

设备最开始位于满足  的下标  处。之后共进行  次移动，每次按照下面的规则前往下一个检测点：

• 设当前所在位置的下标为 ；
• 找到唯一的下标 ，满足 ；
• 从下标  移动到下标 。

如果 $t左移动；如果 ，则记作一次向右移动。

请统计完成全部巡检后，向左移动和向右移动分别发生了多少次。

输入描述

第一行读入一个整数 （），表示检测点的数量。

第二行读入  个整数 ，它们构成一个  的排列。

输出描述

输出一行两个非负整数，依次表示整个巡检过程中向左移动的次数和向右移动的次数。

样例1

输入

52 4 1 5 3

输出

2 2

说明

各序号所在的下标依次为 。

因此移动过程为 ，其中 、 向左，共  次；另外两次移动向右，所以输出 2 2。

样例2

输入

63 6 1 5 2 4

输出

3 2

说明

序号  所在的位置依次为 ，移动轨迹为

。

其中有  次移动到更小的下标，有  次移动到更大的下标，因此答案为 3 2。

题解

解题思路

由于数组是一个排列，所以每个序号都只出现一次。

可以先预处理一个位置数组 ，其中  表示数字  在排列中的下标。

之后按照巡检顺序从  枚举到 ：

• 如果 ，说明从序号  移动到序号  时向左移动。
• 如果 ，说明这次向右移动。

因此只需要先记录每个数字的位置，再进行一次线性扫描即可。

使用的算法为排列逆映射与线性枚举。

复杂度分析

建立位置数组需要  的时间，统计移动方向也需要  的时间，因此总时间复杂度为 。

位置数组需要保存  个元素，因此空间复杂度为 。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

defsolve(p):    n = len(p)# pos[x] 表示数字 x 所在的位置    pos = [0] * (n + 1)for i in range(n):        pos[p[i]] = i    left = 0    right = 0# 按照 1 -> 2 -> ... -> n 的顺序移动for x in range(1, n):if pos[x + 1] < pos[x]:            left += 1else:            right += 1return left, rightdefmain():    n = int(input())    p = list(map(int, input().split()))    left, right = solve(p)    print(left, right)if __name__ == "__main__":    main()

第2题-监测样本偏离判定

题目内容

某监测系统积累了一批处于稳定状态下的历史传感数据，这些记录均可视为正常样本。现在系统收到一批新的监测记录，希望根据历史数据所形成的主要变化模式，判断新记录是否出现明显偏离。

请在仅使用  的前提下，实现一个基于  重建误差的异常检测方法，并对每个待检测样本给出判定结果。

已知参考数据中只包含正常样本，而待检测数据中可能同时存在正常样本和异常样本。整个处理过程必须严格按照下面的步骤进行。

1. 缺失值补全

设参考矩阵为 ，待检测矩阵为 。

对于第  列特征，计算参考矩阵该列所有非缺失元素的均值，记为 。

随后：

• 参考矩阵第  列中的缺失值全部使用  补全；
• 待检测矩阵第  列中的缺失值也必须使用相同的  补全。

补全后的两个矩阵仍记作  和 。

其中：

•  为参考样本数量；
•  为待检测样本数量；
•  为特征维度。

2. 标准化

使用 StandardScaler 对数据进行标准化。

StandardScaler 只能在参考矩阵  上执行 fit，之后分别对  和  执行 transform。

标准化后的矩阵分别记为  和 。

若参考数据第  个特征的均值和标准差分别为 、，则有：

以及：

注意，待检测数据不能单独计算均值或标准差。

3. PCA 投影与重建

仅使用标准化后的参考矩阵  训练 。

参数固定为：

• n_components=0.95
• svd_solver='full'

这表示保留累计解释方差比达到或超过  所需要的最少主成分数量。

将  投影到得到的主成分空间后再执行逆变换，记重建结果为 。

使用同一个已经训练完成的  对  进行投影和逆变换，得到 。

整个过程中，不允许使用待检测数据重新训练或调整 。

4. 偏离分数

一个样本的偏离分数定义为它与 PCA 重建结果之间各维平方差之和。

对于第  个参考样本：

对于第  个待检测样本：

因此，全部参考样本对应的偏离分数组成：

5. 判定边界

使用全部参考样本的偏离分数计算判定边界 。

必须按照下面的方式得到：

np.percentile(D_ref, 95)

即：

对于第  个待检测样本，其输出标签定义为：

其中：

•  表示该样本判定为正常；
•  表示该样本判定为异常。

注意，当偏离分数恰好等于  时，该样本仍判定为正常。

输入描述

标准输入为 JSON，格式如下：

{"train": [[f11, f12, ..., f1d],              [f21, f22, ..., f2d],              ...],"test": [[g11, g12, ..., g1d],             [g21, g22, ..., g2d],             ...]}

其中：

• train：二维列表，大小为 ，其中所有样本均为正常样本；
• test：二维列表，大小为 ，包含需要判定的样本；
• 每个特征值可能是整数、浮点数或 null；
• train 与 test 的特征列数完全相同；
• ；
• ；
• 。

输出描述

输出一个 JSON 数组，其中依次存放所有待检测样本的判定标签。

例如：

[0, 1, 0]

其中：

•  表示正常；
•  表示异常。

标签的顺序必须与输入中 test 的样本顺序保持一致。（标签之间有空格）

补充说明

• 仅允许使用 ；
• 缺失值所使用的均值只能来自训练数据；
• StandardScaler 和 PCA 均只能在训练数据上进行拟合；
• PCA 参数必须为 n_components=0.95、svd_solver='full'；
• 判定边界必须使用 np.percentile(D_ref, 95)；
• 不得改用 IsolationForest、One-Class SVM、RobustScaler 等其他异常检测或预处理方法。

样例1

输入

{"train": [[1,2],[2,4.1],[3,5.9],[4,8.1],[5,10]],"test": [[2.5,5.0],[2.5,10.0],[3.0,null]]}

输出

[0, 1, 0]

说明

训练数据的两个特征具有较明显的共同变化趋势，因此 PCA 可以用较少的主成分描述其主要结构。

第一个待检测样本与训练数据表现出的变化关系接近，其重建偏离较小，因此输出 。

第二个样本的两个特征之间出现了明显不同于参考数据的关系，PCA 重建后的平方误差和超过训练误差的  分位数，因此输出 。

第三个样本的第二维为 null，需要先使用训练数据第二维特征的均值进行补全，再执行标准化和 PCA 重建。其最终偏离分数没有超过判定边界，因此输出 。

题解

解题思路

本题使用  重建误差进行异常检测。

训练集全部由正常样本组成，因此可以利用训练集学习正常数据的主要特征结构。如果一个测试样本与正常数据差异较大，那么经过  降维并重建后，它的重建误差通常也会更大。

具体按照以下步骤处理：

 缺失值填充。

先计算训练集每一列的均值。训练集和测试集中的缺失值，都使用对应列的训练均值填充。

这样可以保证测试集不会参与任何统计量的计算。

 标准化。

使用 StandardScaler，只在训练集上执行 fit，然后分别对训练集和测试集执行 transform。

 训练 。

在标准化后的训练集上建立 PCA，参数固定为：

PCA(n_components=0.95, svd_solver='full')

这样会自动选择累计解释方差比达到  所需的最少主成分。

之后分别将训练集和测试集进行：

transform -> inverse_transform

得到对应的重建数据。

 计算重建误差。

对于一个样本，将标准化后的原数据与重建数据对应位置作差，计算平方和：

分别得到所有训练样本和测试样本的重建误差。

 确定异常阈值。

将所有训练样本的重建误差记为 ，按照题目要求使用：

np.percentile(E_train, 95)

得到阈值 。

对于每个测试样本：

• 若重建误差大于 ，输出 ；
• 否则输出 。

需要特别注意，误差等于阈值时仍然属于正常样本，因此代码中必须使用严格的大于号 >。

复杂度分析

设训练样本数为 ，测试样本数为 ，特征数为 ，最终保留的主成分数量为 。

缺失值处理和标准化的时间复杂度为：

使用 svd_solver='full' 训练  时，需要进行完整奇异值分解，其时间复杂度可以表示为：

训练集和测试集进行投影、重建以及计算误差的时间复杂度为：

因此总体时间复杂度主要由  的完整奇异值分解决定。

空间复杂度主要用于保存训练集、测试集以及  的主成分矩阵，为：

本题中 、、 都很小，因此该复杂度完全可以满足要求。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

import jsonimport sysimport numpy as npfrom sklearn.preprocessing import StandardScalerfrom sklearn.decomposition import PCAdefdetect_anomaly(train, test):# 转为浮点数组，JSON 中的 null 会转换为 nan    X = np.array(train, dtype=float)    T = np.array(test, dtype=float)# 计算训练集每一列的均值    means = np.nanmean(X, axis=0)# 使用训练均值填充训练集缺失值    row, col = np.where(np.isnan(X))    X[row, col] = means[col]# 使用相同的训练均值填充测试集缺失值    row, col = np.where(np.isnan(T))    T[row, col] = means[col]# 标准化，只在训练集上拟合    scaler = StandardScaler()    X_scaled = scaler.fit_transform(X)    T_scaled = scaler.transform(T)# PCA 只在训练集上训练    pca = PCA(n_components=0.95, svd_solver='full')    pca.fit(X_scaled)# PCA 投影并重建    X_rebuilt = pca.inverse_transform(pca.transform(X_scaled))    T_rebuilt = pca.inverse_transform(pca.transform(T_scaled))# 计算每个样本的重建误差    train_error = np.sum((X_scaled - X_rebuilt) ** 2, axis=1)    test_error = np.sum((T_scaled - T_rebuilt) ** 2, axis=1)# 训练误差的 95% 分位数作为阈值    threshold = np.percentile(train_error, 95)# 严格大于阈值才判定为异常return (test_error > threshold).astype(int).tolist()defmain():# 读取 JSON 输入    data = json.loads(sys.stdin.read())    train = data["train"]    test = data["test"]# 进行异常检测    answer = detect_anomaly(train, test)# 按 JSON 数组格式输出    print(json.dumps(answer))if __name__ == "__main__":    main()