笔试时间：2025年8月27日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

KNN 算法的核心思想是，如果一个样本在特征空间中的 K 个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。请按照下面的步骤实现 KNN 算法。

KNN 算法说明：

计算待分类点到其他样本点的距离

通过距离进行排序，选择距离最小的 K 个点

提取这 K 个临近点的类别，根据少数服从多数的原则，将占比最多的那个标签赋值给待分类样本点的 label

本题说明：

给定数据集中，默认每一类标签都存在数据，不存在某类型数量为 0 的场景

消除不同特征权重问题，给出数据均已做好归一化处理，并保留两位小数

出现并列第一的情形时，取并列第一的样本中，最近邻居的标签返回

距离函数定义为：dₓ,ᵧ是 x 和 y 的距离，计算各维度差的平方和的平方根

输入描述

第 1 行：k m n s - k 代表每次计算时选取的最近邻居个数（不大于 20），m 代表样本数量（不大于 200），n 代表样本维度（不包括标签，不大于 5），s 代表类别个数（不大于 5）

第 2 行：待分类样本

第 3 行～第 m + 2 行：m 个样本，每一行 n + 1 列，最后一列为类别标签 label

输出描述

输出待分类样本的类别标签及距离最小的 K 个点中的该标签样本数量

样例输入

3 10 2 3

0.81 0.64

0.19 0.2 1.0

0.18 0.14 0.0

0.76 0.58 1.0

0.4 0.16 1.0

0.98 0.85 0.0

0.42 0.97 1.0

0.75 0.26 1.0

0.24 0.06 1.0

0.97 0.8 0.0

0.21 0.1 2.0

样例输出

0 2

说明：第 1 行输入说明输入了 m = 10 个样本，每个样本有 n = 2 个维度的数据（去除最后一列标签），共有 s = 3 种类别第 2 行输入待分类样本的 n 维数据从第 3 行到第 12 行的前两列数据为输入的 m = 10 个样本，每个样本有 n = 2 个维度的数据 + 最后一列的标签数据待分类样本 [0.81 0.64] 最近的前 k = 3 个邻居分别为：[0.76 0.58]，[0.98 0.85]，[0.97 0.8]，分别有 2 个 0 号标签和 1 个 1 号标签，0 号标签占多，返回 0 以及标签 0 的样本数量 2。

参考题解

这道题考察的是 KNN（K-近邻）算法 的基本实现。

Python：

import math
from collections import defaultdict


def d(p, q):
    r = 0.0
    for i in range(len(p)):
        r += (p[i] - q[i]) ** 2
    return math.sqrt(r)


def main():
    k_val, m_val, n_val, s_val = map(int, input().split())

    test_pt = list(map(float, input().split()))

    train_data = []
    for i in range(m_val):
        train_data.append(list(map(float, input().split())))

    dist_list = []
    for pt in train_data:
        feat = pt[:-1]
        lbl = pt[-1]
        dist_val = d(test_pt, feat)
        dist_list.append((dist_val, lbl))

    dist_list.sort(key=lambda x: x[0])

    top_k = dist_list[:k_val]
    labels = [x[1] for x in top_k]

    ifnot labels:
        return

    cnt_map = defaultdict(int)
    for l in labels:
        cnt_map[l] += 1

    max_cnt = 0
    for l in cnt_map:
        if cnt_map[l] > max_cnt:
            max_cnt = cnt_map[l]

    candidates = [l for l, c in cnt_map.items() if c == max_cnt]

    result = -1
    if len(candidates) == 1:
        result = candidates[0]
    else:
        for dist, lbl in top_k:
            if lbl in candidates:
                result