标签在前K个近邻中的出现次数

[编程题]标签在前K个近邻中的出现次数

热度指数：1691 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

你需要为一个简单的多分类识别器补上“K 近邻”判别模块。做法是：先度量待测样本与训练样本的距离，挑选出距离最近的 K 个样本，再用多数票决定最终类别。
操作要点（按流程执行）：
- 先计算待测点到每个样本点的距离（为了效率，可直接用“平方欧氏距离”参与排序，结果等价）。
- 将样本按距离升序排列，截取前 K 个作为近邻。
- 统计这 K 个近邻的标签出现次数，频数最高的标签即为预测值。
- 如出现“最高频数并列”，只在并列标签对应的近邻里，按由近到远的顺序挑第一个的标签。
约束与假设：
- 数据集已做归一化处理（不同维度量纲一致），特征保留两位小数。
- 每个类别在数据集中都至少有一个样本。
- 距离采用欧氏距离： $d(q,x)=\sqrt{\sum_{i=1}^{n}(q_i-x_i)^2}$

输入描述:

第 1 行：k m n s
k 为最近邻个数（≤20），m 为样本数（≤200），n 为特征维度（不含标签，≤5），s 为类别个数（≤5）。
第 2 行：待分类样本的 n 维特征。
第 3 行至第 m+2 行：每行 n+1 列，前 n 列为特征，最后 1 列为类别标签（整数，以浮点给出）。

输出描述:

输出两项：预测标签 与 该标签在前 K 个近邻中的出现次数  
  格式：label count

示例1

输入

3 6 2 2
0.00 0.00
0.20 0.10 0.0
0.30 0.00 0.0
0.00 0.40 1.0
0.60 0.60 1.0
0.05 0.02 0.0
0.90 0.90 1.0

输出

0 3

说明

距离最近的 3 个样本依次为 (0.05,0.02,0), (0.20,0.10,0), (0.30,0.00,0)。  
多数票为标签 0，且在前 K=3 个邻居中出现 3 次，故输出“0 3”。

示例2

输入

4 6 2 3
1.00 1.00
0.95 0.95 2.0
1.10 1.00 2.0
0.90 1.10 1.0
0.80 0.90 1.0
2.00 2.00 3.0
1.30 1.40 1.0

输出

2 2

说明

最近的 4 个邻居按距离为：(0.95,0.95,2)、(1.10,1.00,2)、(0.90,1.10,1)、(0.80,0.90,1)。  
标签 1 与 2 在前 K=4 中均出现 2 次，构成并列；比较并列集合中“最近”的样本，其最近者为 (0.95,0.95,2)，因此最终返回标签 2；同时输出该标签在前 K 中出现的次数 2。