通过率 75% · 提交 8 · 通过 6
在推荐系统和图像检索等 AI 应用中,一个核心操作是近邻检索:给定一个查询特征向量,在海量候选向量中找到与之最相似的若干个。 相似度采用欧氏距离衡量:对于两个 d 维整数向量 A = (a_1, a_2, ..., a_d) 和 B = (b_1, b_2, ..., b_d),它们的欧氏距离定义为: dist(A, B) = sqrt((a_1 - b_1)^2 + (a_2 - b_2)^2 + ... + (a_d - b_d)^2)
距离越小表示两个向量越相似。 现给定 n 个候选特征向量和 1 个查询向量,请找出与查询向量欧氏距离最近的 k 个候选向量,按距离从近到远输出它们的编号。
这类题属于算法机考高频题型中「100分 / 华为OD」方向的高频题型,通常考察对「100分 / 华为OD」的建模能力与边界条件处理。掌握本题的解题思路后,可举一反三应对同类真题方向,稳步提升机考通过率。
第一行:n d k
一维数组 idx_1, idx_2, ..., idx_k 最近的 k 个候选向量编号(编号从 1 开始),按距离升序排列 距离相同时编号小的排前面
示例 1
输入示例
4 2 2 1,2 4,6 2,3 5,5 3,4
输出示例
3,2
查询向量为 (3, 4),各候选向量的欧氏距离平方计算如下:
| 编号 | 向量 | 距离平方 | 距离 |
|---|---|---|---|
| 1 | (1, 2) | (3−1)²+(4−2)²=8 | √8≈2.83 |
| 2 | (4, 6) | (3−4)²+(4−6)²=5 | √5≈2.24 |
| 3 | (2, 3) | (3−2)²+(4−3)²=2 | √2≈1.41 |
| 4 | (5, 5) | (3−5)²+(4−5)²=5 | √5≈2.24 |
按距离从小到大为 3 2 4 1,取前两个 3 2
示例 2
输入示例
5 2 4 1,0 0,1 -1,0 0,-1 5,5 0,0
输出示例
1,2,3,4
查询向量为 (0, 0)。候选 1~4 的距离平方都是 1,候选 5 的距离平方是 50。前 4 个距离相同,按编号从小到大排列,结果为 [1, 2, 3, 4]。
时间限制 1000 ms · 内存限制 256 MB
本平台为独立第三方培训机构,与华为技术有限公司无任何关联;课程的服务内容与权益以购买协议为准,学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述,相关商标归各自权利人所有。
登录后可查看你在本题的历史提交,以及每次的各用例通过情况。
示例 3
输入示例
3 2 3 1,1 2,2 3,3 0,0
输出示例
1,2,3
© 2026 广州慕课网络科技有限公司 · 吴师兄学算法官网 版权所有