华为 · 计算几何 · 算法编程题
华为 计算几何 N ≤ 1e5 时限 3 秒 / 256 MB

题目描述

小红正在研发一款部署在智能音箱上的语音意图识别系统。该系统的核心逻辑是将用户输入的语音信号转化为一个三维特征向量，并通过比较该向量与已知样本库中向量的距离来进行分类。
具体而言，小红采用了 K 最近邻（KNN）算法。对于一个待识别的特征向量，系统会在样本库中寻找欧氏距离最近的 K 个已知样本。接着，系统会统计这 K 个样本所属的意图类别标签，并将出现频率最高的标签作为预测结果。如果存在多个类别标签的出现次数相同且均为最高，小红规定输出其中数值最小的那个标签。
题目保证在距离第 K 近的边界上不会出现多个样本距离相等而导致的歧义。

输入输出

输入描述
第一行包含两个正整数 N 和 K，分别表示样本库中已知语音特征向量的数量，以及分类时需要参考的最近邻个数（ 1 ≤ K ≤ N ≤ 10^5 ）。
接下来的 N 行，每行包含三个浮点数 x1, x2, x3 和一个整数 label。其中 (x1, x2, x3) 是特征向量在三维空间中的坐标（取值范围在 -1000.0 到 1000.0 之间），label 是该样本对应的意图类别标签（取值范围为 0 到 10^4 之间的整数）。
最后一行包含三个浮点数，代表当前需要进行意图识别的目标语音特征向量坐标。
输出描述
输出一个整数，代表分类器预测出的意图类别标签。

样例共 2 组

样例 1 · 目标特征向量为 (0.1, 0.1, 0.1)。计算它到样本库中四个点的欧氏距离，距离最近的三个样本分别是： 1. (0.0, 0.0, 0.0)，标签为 10； 2. (0.0, 1.0, 0.0)，标签为 10； 3. (1.0, 1.0, 1.0)，标签为 20。 在这三个最近邻中，标签 10 出现了 2 次，标签 20 出现了 1 次。因此，出现次数最多的标签是 10。
输入
4 3
0.0 0.0 0.0 10
1.0 1.0 1.0 20
0.0 1.0 0.0 10
10.0 10.0 10.0 30
0.1 0.1 0.1
输出
10
样例 2 · The target feature vector is (2.2, 2.1, 2.3). Its squared Euclidean distances to the known vectors are calculated. The 3 nearest neighbors are (2.1, 2.3, 2.2) of category 1, (2.3, 2.2, 2.4) of category 1, and (2.2, 2.4, 2.3) of category 1. Since all 3 nearest neighbors belong to category 1, the target vector is classified as category 1.
输入
10 3
0.5 0.3 0.4 0
0.6 0.2 0.5 0
0.4 0.3 0.3 0
0.7 0.4 0.6 0
2.1 2.3 2.2 1
2.3 2.2 2.4 1
2.2 2.4 2.3 1
4.5 4.3 4.4 2
4.4 4.5 4.6 2
4.6 4.4 4.5 2
2.2 2.1 2.3
输出
1

算法解析依据一般

考点：计算几何

数据规模 N ≤ 1e5 ｜ 限制 3 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：K ≤ 1e5，N ≤ 1e5
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：3 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：计算几何

把几何关系转成坐标运算，用整数运算避免浮点误差。

思路框架（计算几何 通法 · 非本题专属）

  1. 把点、向量、线段用坐标表示。
  2. 几何判定（平行、垂直、共线、相交）尽量用叉积/点积的整数形式：叉积为 0 即共线。
  3. 距离用平方比较，避免开方带来的浮点误差。
  4. 面积用叉积（鞋带公式）计算。

实现要点：叉积 cross = x1*y2 - x2*y1；用它判断顺时针/逆时针和共线。

复杂度：时间 O(n) ~ O(n²) ｜ 空间 O(n)

该范式的通法易错点

  • 用浮点相等判断几何关系（应用整数叉积）。
  • 没考虑三点共线、重合等退化情况。

对照本题

  • 数据规模 N ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

样例 1：输入 4 3 / 0.0 0.0 0.0 10 / 1.0 1.0 1.0 20 / 0.0 1.0 0.0 10 / 10.0 10.0 10.0 30 / 0.1 0.1 0.1 → 输出 10

目标特征向量为 (0.1, 0.1, 0.1)。计算它到样本库中四个点的欧氏距离，距离最近的三个样本分别是：

  1. (0.0, 0.0, 0.0)，标签为 10；
  2. (0.0, 1.0, 0.0)，标签为 10；
  3. (1.0, 1.0, 1.0)，标签为 20。

在这三个最近邻中，标签 10 出现了 2 次，标签 20 出现了 1 次。因此，出现次数最多的标签是 10。

样例 2：输入 10 3 / 0.5 0.3 0.4 0 / 0.6 0.2 0.5 0 / 0.4 0.3 0.3 0 / 0.7 0.4 0.6 0 / 2.1 2.3 2.2 1 / 2.3 2.2 2.4 1 → 输出 1

The target feature vector is (2.2, 2.1, 2.3). Its squared Euclidean distances to the known vectors are calculated. The 3 nearest neighbors are (2.1, 2.3, 2.2) of category 1, (2.3, 2.2, 2.4) of category 1, and (2.2, 2.4, 2.3) of category 1. Since all 3 nearest neighbors belong to category 1, the target vector is classified as category 1.

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2026年-华为-03月14号AI岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解