大厂真题 / OPPO

OPPO 8.8 笔试真题 - AI 算法岗

本场考试概述

考试时间：2026年8月8日

考试岗位：AI 算法岗（B 卷）

考试方向：编程题、机器学习工程实现

难度评级：中等偏易

本页收录考点：

第一题：逆排列映射、线性扫描计数（难度简单）
第二题：训练集统计量、StandardScaler、PCA 重建误差与分位数阈值（难度中等）

建议策略：

第一题不要在每次移动时重新搜索下一个序号的位置。先建立“序号到下标”的逆映射，再比较相邻序号的位置即可
第二题应严格复现指定流水线：缺失值均值、标准化器、PCA 和阈值都只能由训练集得到
判定异常时必须使用严格大于阈值；误差恰好等于阈值的样本仍是正常样本

本页仅整理题目信息完整、能够独立验证的两道题。

第 1 题：序号巡检轨迹

题目描述

一条线性巡检带上从左到右设置了 $n$ 个检测点，下标为 $1,2,\ldots,n$。每个检测点被分配了一个唯一的巡检序号。

给定一个长度为 $n$ 的排列 $p$，其中 $1$ 到 $n$ 的每个整数都恰好出现一次，$p_i$ 表示下标 $i$ 处检测点的巡检序号。

巡检设备最开始位于序号 $1$ 所在的位置。随后，它严格按照巡检序号从小到大的顺序移动：从序号 $v$ 所在的位置前往序号 $v+1$ 所在的位置，其中 $1\le v<n$。

若下一位置的下标小于当前位置，则记作一次向左移动；若下一位置的下标大于当前位置，则记作一次向右移动。

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

输入描述

第一行输入一个整数 $n$，表示检测点数量，其中 $1\le n\le 380000$。

第二行输入 $n$ 个整数 $p_1,p_2,\ldots,p_n$，它们构成一个 $1$ 到 $n$ 的排列。

输出描述

输出一行两个非负整数，依次表示向左移动次数和向右移动次数。

样例

输入

5
2 4 1 5 3

输出

2 2

样例解释

序号 $1,2,3,4,5$ 所在的下标依次为 $3,1,5,2,4$，所以设备的移动轨迹为：

\[3\to1\to5\to2\to4\]

其中 $3\to1$、$5\to2$ 是向左移动，另外两次是向右移动，因此输出 2 2。

样例 2

输入

6
3 6 1 5 2 4

输出

3 2

样例解释

序号 $1$ 到 $6$ 所在的位置依次为 $3,5,1,6,4,2$，移动轨迹为：

\[3\to5\to1\to6\to4\to2\]

其中三次移动到更小的下标、两次移动到更大的下标，因此输出 3 2。

思路分析

设备的访问顺序固定为 $1,2,\ldots,n$。真正需要的不是“某个位置上是什么序号”，而是“某个序号位于什么位置”。

建立逆排列 pos：

\[pos[p_i]=i\]

于是第 $v$ 次移动就是从 pos[v] 移动到 pos[v + 1]：

若 pos[v + 1] < pos[v]，向左次数加一
否则向右次数加一

因为 $p$ 是排列，不同序号的位置必然不同，不存在原地不动。总移动次数始终是 $n-1$，也可以只统计左移次数，再用 $n-1-left$ 得到右移次数。

直接按照题意在排列中反复寻找下一个序号，每次搜索需要 $O(n)$，总复杂度会退化为 $O(n^2)$；当 $n$ 达到 $380000$ 时不可行。逆排列把每次位置查询降为 $O(1)$。

正确性证明

对每个序号 $v\in[1,n]$，构造过程令 pos[v] 等于满足 $p_i=v$ 的唯一位置 $i$，因此 pos 准确记录了每个序号所在的下标。

巡检设备严格按 $1,2,\ldots,n$ 的顺序访问，所以对于每个 $v\in[1,n-1]$，它的第 $v$ 次移动必然从 pos[v] 到 pos[v + 1]。算法比较的正是这两个下标：目标下标较小时计入左移，较大时计入右移，与题目定义完全一致。

算法遍历了全部 $n-1$ 对相邻序号，每次移动被统计且仅被统计一次，因此最终得到的左移次数和右移次数正确。

题解代码

import sys


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n = data[0]
    p = data[1:1 + n]

    # pos[v] 表示巡检序号 v 所在的下标。
    pos = [0] * (n + 1)
    for index, value in enumerate(p, start=1):
        pos[value] = index

    left = 0
    for value in range(1, n):
        if pos[value + 1] < pos[value]:
            left += 1

    right = (n - 1) - left
    print(left, right)


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：$O(n)$。建立逆排列和扫描相邻序号各进行一次线性遍历。

空间复杂度：$O(n)$。输入排列与逆排列均为线性规模；若不计输入存储，额外空间为 $O(n)$。

易错点

设备按巡检序号递增访问，不是按检测点下标从左到右访问
不要为每个 value + 1 调用线性查找，否则会退化为 $O(n^2)$
pos 存的是“序号到位置”的逆映射，赋值应为 pos[p[i]] = i
一共有 $n-1$ 次移动，循环范围不能多算或少算
当 $n=1$ 时没有移动，应输出 0 0
题目中的下标从 $1$ 开始；代码可以统一采用一基下标，避免混用造成比较错误

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

题目描述

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

请仅使用 NumPy、pandas、scikit-learn，实现一个基于 PCA 重建误差的异常检测方法。设训练矩阵为 $R\in\mathbb{R}^{n\times d}$，待检测矩阵为 $Q\in\mathbb{R}^{m\times d}$，处理流程必须严格遵循以下步骤。

1. 缺失值补全

对第 $j$ 列，使用训练集该列所有非缺失元素的均值

\[\mu_j=\operatorname{mean}\{R_{ij}\mid R_{ij}\text{ 非缺失}\}\]

补全训练集和测试集第 $j$ 列中的所有缺失值。测试集不能使用自己的均值。

2. 标准化

创建 StandardScaler，只能在补全后的训练集上 fit，再分别对训练集和测试集执行 transform。测试集不能单独拟合标准化器。

3. PCA 投影与重建

只在标准化训练集上拟合：

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

n_components=0.95 表示保留累计解释方差比达到或超过 $95\%$ 所需的最少主成分。训练集和测试集都使用同一个 PCA 先 transform，再 inverse_transform 得到重建结果。

4. 偏离分数

样本的偏离分数是标准化样本与其 PCA 重建结果之间的平方误差和。若标准化后的样本为 $x$、重建结果为 $\hat{x}$，则

\[D(x)=\sum_{j=1}^{d}(x_j-\hat{x}_j)^2\]

5. 判定边界

用全部训练样本的偏离分数计算阈值：

tau = np.percentile(train_scores, 95)

待检测样本的分数严格大于 $\tau$ 时输出 1，表示异常；否则输出 0，表示正常。分数恰好等于阈值时仍输出 0。

输入描述

标准输入为一个 JSON 对象，格式如下：

{
  "train": [[f11, f12], [f21, f22]],
  "test": [[g11, g12], [g21, g22]]
}

其中：

train 是 $n\times d$ 的二维列表，所有样本均为正常样本
test 是 $m\times d$ 的二维列表，包含需要判定的样本
每个特征值可以是整数、浮点数或 null
train 与 test 的特征维度相同
$2\le n,m\le18$，$2\le d\le8$

仅允许使用 NumPy、pandas、scikit-learn。不得改用其他预处理方法或异常检测模型。

输出描述

输出一个 JSON 数组，依次给出所有测试样本的标签。0 表示正常，1 表示异常，顺序必须与输入中的 test 一致。

样例

输入

{"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 可以用较少的主成分描述其主要结构。

第一个测试样本接近训练数据表现出的变化关系，重建误差未超过训练误差的 $95$ 分位数，判为正常
第二个样本的两个特征关系明显偏离训练模式，重建误差严格超过阈值，判为异常
第三个样本的第二维为 null，必须先用训练数据第二维的均值补全，再做标准化和 PCA 重建；其误差未超过阈值，判为正常

因此输出 [0, 1, 0]。

思路分析

这道题不需要选择模型，关键是准确实现题目锁定的数据处理流水线，并防止测试数据泄漏。

第一步：解析 JSON 并按训练均值补全

将 null 转成浮点矩阵中的 np.nan，再用 np.nanmean(train, axis=0) 计算训练集列均值。对训练矩阵和测试矩阵中的缺失位置，都按列填入同一组均值。

第二步：仅用训练集拟合 StandardScaler

标准化消除各特征量纲差异。使用 fit_transform(train) 得到标准化训练集，但测试集只能调用 transform(test)。如果对测试集调用 fit_transform，就会引入测试分布信息，并改变其与训练模型之间的参照口径。

第三步：仅用训练集拟合指定 PCA

以 n_components=0.95, svd_solver="full" 拟合标准化训练集。PCA 保留训练数据的主要变化子空间。样本投影后再逆变换，相当于用这个子空间重建原样本；偏离正常结构越明显，无法被主子空间解释的残差通常越大。

第四步：计算训练误差和测试误差

对每一行计算各维重建残差的平方和，分别得到长度为 $n$ 和 $m$ 的分数数组。

第五步：训练误差定阈值并输出

严格使用 np.percentile(train_scores, 95) 计算阈值。逐个判断 test_score > threshold，将 NumPy 布尔值转换成普通整数后用 json.dumps 输出。

整条流水线中，训练列均值、标准化参数、PCA 主成分和分位数阈值全部只由训练集产生；测试集只接受既有变换和判定。

正确性说明

下面依次说明算法的每一步都符合题目定义。

算法使用 np.nanmean(train, axis=0) 得到每个特征在训练集非缺失元素上的均值，并用这同一组均值补全训练集与测试集。因此补全规则正确，且测试集没有参与均值估计。
StandardScaler.fit_transform 只作用于补全后的训练集，测试集只调用该标准化器的 transform。所以两组数据都使用训练集的均值和尺度，符合标准化要求。
算法以固定参数 n_components=0.95、svd_solver="full" 仅拟合标准化训练集，并用同一个 PCA 重建训练集和测试集。因此所有投影与重建都基于训练数据形成的主成分空间。
算法对每个样本计算标准化向量与重建向量各维平方差之和，恰好等于题目定义的偏离分数。
算法以全部训练分数的 np.percentile(..., 95) 作为阈值，并且仅在测试分数严格大于阈值时输出 1。所以等于阈值的样本输出 0，判定边界也与题意一致。

综上，算法对每个测试样本输出的标签都严格遵循题目指定流程，因此结果正确。

题解代码

import json
import sys

import numpy as np
from sklearn.decomposition import PCA
from sklearn.preprocessing import StandardScaler


def fill_missing_with_train_mean(
    train: np.ndarray, test: np.ndarray
) -> tuple[np.ndarray, np.ndarray]:
    """只使用训练集非缺失值的列均值补全两组数据。"""
    column_means = np.nanmean(train, axis=0)
    # 若训练集某列全部缺失，按题意的退化规则使用 0 补全。
    column_means = np.where(np.isnan(column_means), 0.0, column_means)

    train = train.copy()
    test = test.copy()

    train_rows, train_cols = np.where(np.isnan(train))
    train[train_rows, train_cols] = column_means[train_cols]

    test_rows, test_cols = np.where(np.isnan(test))
    test[test_rows, test_cols] = column_means[test_cols]

    return train, test


def solve() -> None:
    raw = json.load(sys.stdin)

    # JSON 中的 null 会被解析为 None；转换到 float 数组时成为 np.nan。
    train = np.asarray(raw["train"], dtype=float)
    test = np.asarray(raw["test"], dtype=float)

    # 1. 缺失值补全：填充值只能来自训练集。
    train, test = fill_missing_with_train_mean(train, test)

    # 2. 标准化：StandardScaler 只能在训练集上 fit。
    scaler = StandardScaler()
    train_scaled = scaler.fit_transform(train)
    test_scaled = scaler.transform(test)

    # 3. PCA：固定参数，且只能在标准化训练集上 fit。
    pca = PCA(n_components=0.95, svd_solver="full")
    pca.fit(train_scaled)

    train_rebuilt = pca.inverse_transform(pca.transform(train_scaled))
    test_rebuilt = pca.inverse_transform(pca.transform(test_scaled))

    # 4. 每行各维重建残差的平方和。
    train_scores = np.sum((train_scaled - train_rebuilt) ** 2, axis=1)
    test_scores = np.sum((test_scaled - test_rebuilt) ** 2, axis=1)

    # 5. 训练误差的 95 分位数；必须严格大于阈值才是异常。
    threshold = np.percentile(train_scores, 95)
    labels = [int(score > threshold) for score in test_scores]

    print(json.dumps(labels))


if __name__ == "__main__":
    solve()

复杂度分析

令 $r=\min(n,d)$，PCA 最终保留 $k\le r$ 个主成分。

时间复杂度：补全和标准化为 $O((n+m)d)$；svd_solver="full" 对 $n\times d$ 训练矩阵做完整 SVD，复杂度为 $O(nd\min(n,d))$；训练集与测试集投影、重建为 $O((n+m)dk)$。整体可写为

\[O\bigl(nd\min(n,d)+(n+m)dk\bigr)\]

在本题 $n,m\le18$、$d\le8$ 的范围内，开销很小。

空间复杂度：$O((n+m)d+d k)$，用于保存两组数据、标准化与重建结果以及 PCA 主成分。

易错点

测试集缺失值必须用训练集列均值补全，不能用测试集自己的均值
应先完成缺失值补全，再进行 StandardScaler 和 PCA
StandardScaler 只能在训练集上 fit；测试集只能 transform
PCA 同样只能在训练集上拟合，参数必须精确写成 PCA(n_components=0.95, svd_solver="full")
重建误差是在标准化空间中计算，不应拿原始数据与标准化后的重建值比较
分数是各维平方差之和，不是均方误差、欧氏距离或绝对误差
阈值必须使用训练分数的 np.percentile(train_scores, 95)，不能从测试分数计算
判定条件必须是 score > threshold，不能写成 >=
输出应保持测试样本原顺序，并转换为普通整数，避免输出 NumPy 类型或布尔值
不要改用 RobustScaler、IsolationForest、One-Class SVM 等其他方法

知识点总结

题目	核心考点	关键结论
序号巡检轨迹	逆排列、线性扫描	建立 `pos[p[i]] = i`，轨迹就是 `pos[1], pos[2], ..., pos[n]`
监测样本偏离判定	训练集统计量、标准化、PCA 重建误差、分位数	所有拟合与阈值都只依赖训练集；测试误差严格大于训练误差 95 分位才判异常

第一题的关键是把反复搜索改造成一次预处理后的常数时间查询；第二题的关键则是避免任何形式的数据泄漏，并逐字落实指定参数、误差定义和边界比较。前者考查复杂度意识，后者考查机器学习流水线的工程严谨性。

这篇文章有帮助吗？

| GitHub 留言