首页 > 试题广场 >

标签在前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。

备注:

本题由牛友@Charles 整理上传

算法知识视频讲解

起一个响亮的名字真的很难

import sys
import math

data = sys.stdin.read().split()
ptr = 0
k, m, n, s = int(data[ptr]), int(data[ptr+1]), int(data[ptr+2]), int(data[ptr+3])
ptr += 4
x = list(map(float, data[ptr:n+ptr]))
ptr += n
simple = []
for i in range(m):
s = list(map(float, data[ptr:ptr+n+1]))
ptr += n+1
simple.append(s)

D = []
for i in range(m):
dd = 0
for j in range(n):
dd += (simple[i][j] - x[j])**2
simple[i].append(dd)

simple.sort(key=lambda x: x[n+1])

short = simple[0:k]
L = {}
for x in short:
if x[n] in L:
L[x[n]] += 1
else:
L[x[n]] = 1

max_count = max(L.values())
candidates = [label for label, count in L.items() if count == max_count]

pred = None
for label in short:
if label[n] in candidates:
pred = int(label[n])
break
print('{} {}'.format(pred,max_count))

发表于 2025-08-31 21:31:17 回复(0)

牛客503059521号

有个问题，以下是我的代码：

tmp = input().split()

k, m, n, s = [int(x) for x in tmp]

feature = input().split()

feature = [float(x) for x in feature]

data = []

def get_dis(l1, l2):

return sum([(x - y) ** 2 for x, y in zip(l1, l2)])

for i in range(m):

tmp = input().split()

tmp = [float(x) for x in tmp]

data.append((get_dis(tmp[:-1], feature), tmp[-1]))

data.sort()

top_k = data[:k]

labels = [x[1] for x in top_k]

vote = []

for i in range(s):

vote.append(len([x for x in labels if x == i]))

print(vote.index(max(vote)), max(vote))

对于数据点

2 3 2 3
0.05 0.05
0.04 0.05 1.0
0.06 0.05 2.0
0.20 0.20 2.0

预期输出2 1，我的输出1 1

但题目没有提到该如何处理最高频数并列，且距离相同时该如何处理？

发表于 2025-10-22 05:59:54 回复(0)

Oiiiiiiii

import sys
import math
from collections import Counter
def read():
k, m, n, s = map(int,input().split())
sample = list(map(float,input().split()))
trs = []
for _ in range(m):
trs.append(list(map(float,input().split())))
return k, m, n, s, sample, trs

def distance(sample,tr):
d = 0
for i in range(n):
d += (sample[i] - tr[i]) ** 2
return math.sqrt(d)

def d_label(sample,trs):
d = []
for i in range(m):
tr = trs[i]
dis = distance(sample,tr)
lable = tr[-1]
d.append((dis, lable))
d.sort(key= lambda a: a[0])
return d[:k]
def count_label(d):
labels = []
for _,label in d:
labels.append(int(label))
cnt = Counter(labels)
max_elem, max_cnt = cnt.most_common(1)[0]
return max_elem, max_cnt

if __name__ == "__main__":
k, m, n, s, sample,trs = read()

d_la = d_label(sample,trs)
label,count = count_label(d_la)
print(label,count)

发表于 2025-10-09 18:07:59 回复(0)

学术傻龙

# 用不了numpy是认真的吗

importsys

from collections importCounter, defaultdict

importmath

k, m, n, s = map(int, input().split())

# k 为最近邻个数（≤20），m 为样本数（≤200），n 为特征维度（不含标签，≤5），s 为类别个数（≤5）。

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

# 第 2行：待分类样本的 n 维特征。

x, y = [], []

for_ in range(m):

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

x.append(input_lst[:n])

y.append(input_lst[-1])

# 第 3行至第 m+2行：每行 n+1列，前 n 列为特征，最后 1列为类别标签（整数，以浮点给出）。

trains, labels = x, y

dis = []

forsample, label in zip(trains, labels):

dist = 0.

forj in range(n):

dist+= (x_test[j]-sample[j])**2# 计算每个维度上的距离

dist = math.sqrt(dist)

dis.append((dist, label))

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

k_nearest = dis[:k] # 取前k个

k_label_count = defaultdict(int)

for_, label in k_nearest:

k_label_count[label] += 1

max_count = max(k_label_count.values())

# 找出频数最高的候选标签

candidates = [label forlabel, count in k_label_count.items() ifcount == max_count]

iflen(candidates) == 1:

print(int(candidates[0]), end=' ')

print(max_count)

else:

forlabel in k_label_count:

iflabel in candidates:

print(int(label), end=' ')

print(max_count)

break

发表于 2025-09-20 21:08:24 回复(0)

dundunnp

import sys
import math
input = sys.stdin.readline

def distance(attr: List[float], data: List[float]) -> float:
    return math.sqrt(sum((x - y) ** 2 for x, y in zip(attr, data)))

k, m, n, s = map(int, input().split())
attr = list(map(float, input().split()))
h = []
for _ in range(m):
    data = list(map(float, input().split()))
    label = int(data.pop())
    h.append((distance(attr, data), label))

h = sorted(h)[:k]

labels = [0] * s
for _, label in h:
    labels[label] += 1

ans_labels = []
max_cnt = 0
for i, x in enumerate(labels):
    if x > max_cnt:
        ans_labels = [i]
        max_cnt = x
    elif x == max_cnt:
        ans_labels.append(i)

if len(ans_labels) == 1:
    print(ans_labels[0], max_cnt)
else:
    ans_label = -1
    for _, label in h:
        if label in ans_labels:
            ans_label = label
            break
    print(ans_label, max_cnt)

发表于 2025-09-05 13:38:42 回复(1)

Python

牛客236504888号

import sys
from collections import Counter

def KNN_Classification():
    input_tokens = sys.stdin.read().strip()
    input_tokens = input_tokens.split()
    token_iter = iter(input_tokens)
    k = int(next(token_iter))
    SampleNums = int(next(token_iter))
    FeatureDim = int(next(token_iter))
    ClassNums  = int(next(token_iter))

    test_inputs = [float(next(token_iter)) for _ in range(FeatureDim)]
    train_inputs = []
    train_labels = []
    for _ in range(SampleNums):
        sample_data = [float(next(token_iter)) for _ in range(FeatureDim + 1)]
        train_inputs.append(sample_data[:FeatureDim])
        train_labels.append(int(sample_data[-1]))

    index_list =[]
    distance_list = []
    for i  in range(SampleNums):
        current_feat = train_inputs[i]
        distance = 0
        for j in range(FeatureDim):
            delta = current_feat[j] - test_inputs[j]
            distance += delta*delta
        #L2_norm = 
        distance_list.append((distance,i))
    distance_list.sort(key = lambda x:x[0])
    top_k_index = [distance_list[i][1] for i in range(k)]

    top_k_labels = [train_labels[index] for index in top_k_index]

    labels_counts = Counter(top_k_labels)
    max_frequency = max(labels_counts.values())

    tiled_labels = [labels for labels,freq in labels_counts.items() if freq ==max_frequency] 
    select_label = None
    for i in range(SampleNums):
        current_label = train_labels[distance_list[i][1]]
        if current_label in tiled_labels:
            select_label = current_label
            break
    print(select_label,max_frequency)

if __name__ == '__main__':
    KNN_Classification()

发表于 2025-09-04 21:17:21 回复(0)

Python3

ClydeSpeed

k, m, n, s = map(int, input().split())

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

train_samples = []

for _ in range(m):

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

features = data[:n]

label = int(data[n])

train_samples.append((features, label))

# 计算待测样本到每个训练样本的平方欧氏距离

distances = []

for features, label in train_samples:

sq_dist = sum((test_features[i] - features[i]) ** 2 for i in range(n))

distances.append((sq_dist, label, features))

# 按距离升序排序，取前K个近邻

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

k_nearest = distances[:k]

# 统计前K个近邻中各类别的出现频次

count = {}

for _, label, _ in k_nearest:

count[label] = count.get(label, 0) + 1

max_count = max(count.values())

# 找出具有最高频数的标签

max_labels = [label for label, count in count.items() if count == max_count]

if len(max_labels) == 1:

predicted_label = max_labels[0]

else:

for _, label, _ in k_nearest:

if label in max_labels:

predicted_label = label

break

print(f"{predicted_label} {max_count}")

发表于 2025-09-03 13:36:27 回复(0)

新鲜的肉松饼

import java.util.HashMap;

import java.util.Map;

import java.util.PriorityQueue;

import java.util.Scanner;

class Pair implements Comparable<Pair> {

double k;

double v;

public Pair(double k, double v){

this.k = k;

this.v = v;

}

public void incV (){

this.v ++;

}

@Override

public int compareTo(Pair other){

return Double.compare(this.v, other.v);

}

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

int k = in.nextInt();

int m = in.nextInt();

int n = in.nextInt();

int s = in.nextInt();

double[] target = new double[n];

for (int i = 0; i < n; i++){

target[i] = in.nextDouble();

}

double[] sample;

Pair samplePair;

PriorityQueue<Pair> neighbors = new PriorityQueue<Pair>();

for (int i = 0; i < m; i++){

sample = new double[n + 1];

for (int j = 0; j < n; j++){

sample[j] = in.nextDouble();

}

samplePair = new Pair(in.nextDouble(), calculateDistance(target, sample));

neighbors.offer(samplePair);

}

Map<Double, Pair> knn = new HashMap<Double, Pair>();

Pair current;

int order = 0;

for (int i = 0; i < k; i++){

current = neighbors.poll();

if (!knn.containsKey(current.k)){

knn.put(current.k, new Pair(order, 1));

order ++;

} else {

knn.get(current.k).incV();

}

double times = 0;

double lastOrder = Double.MAX_VALUE;

double label = 0;

Pair currentPair;

for (Double d : knn.keySet()){

currentPair = knn.get(d);

if (currentPair.v > times){

times = currentPair.v;

}

for (Double d : knn.keySet()){

currentPair = knn.get(d);

if (currentPair.v == times && currentPair.k < lastOrder){

lastOrder = currentPair.k;

label = d;

}

System.out.println((int) label + " " + (int) times);

}

public static double calculateDistance(double[] target, double[] sample){

double sum = 0;

for (int i = 0; i < target.length; i++){

sum += Math.pow(target[i] - sample[i], 2) ;

}

return Math.sqrt(sum);

}

发表于 2025-09-02 09:47:29 回复(0)

提交观点

问题信息

难度：

8条回答 24收藏 214浏览

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

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

相关试题