解题思路

核心步骤

1. 读入参数：$k, m, n, s$；读入待分类样本向量 $q$（维度 $n$）；读入 $m$ 条样本（前 $n$ 列为特征，最后一列为标签）。

2. 计算距离：对每个样本 $x$，计算与 $q$ 的欧氏距离

   $$d(q,x)=\sqrt{\sum_{i=1}^{n}(q_i-x_i)^2}$$

题目内容

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

$KNN$ 算法说明：

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

通过距离进行排序，选择距离最小的 $K$ 个点；提取这 $K$ 个临近点的类别，根据少数服从多数的原则，将占比最多的那个标签赋值给待分类样本点的 $label$ 。

本题说明：

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

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

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

4、距离函数定义为: $d_{x,y}=\sqrt{\sum^n_{i=1}(x_i-y_i)^2}$。

输入描述

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

第 $2$ 行：待分类样本

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

输出描述

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

样例1

输入

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$

样例2

输入

6 10 2 4
0.78 0.63
0.57 0.07 1.0
0.5 0.13 1.0
0.83 0.07 3.0
0.27 0.87 3.0
0.81 0.44 2.0
0.21 0.73 3.0
0.45 0.91 1.0
0.12 0.22 2.0
0.25 0.48 0.0
0.54 0.87 1.0

输出

1 2

说明

本样例的距离最小的 $6$ 个样本中，标签 $1$ 和标签 $3$ 出现次数都是 $2$ 次，并列第一；虽然 $[0.8$ $0.44]$ 距离样本最近，但其标签 $2$ 不是出现最多的，排除在下一轮统计样本中此时需要从标签 $1$ 和标签 $3$ 中的样本中，选取距离最近的 $[0.54$ $0.87]$ 的标签 $1$ 作为返回值，并同时返回标签 $1$ 的样本数量 $2$ 。