Problema
Os k vizinhos mais próximos (KNN) classificam um ponto novo olhando os k pontos de treinamento mais próximos e escolhendo o rótulo mais comum.
- Calcule a distância euclidiana de
queryaté cada ponto. - Ordene os pontos pela distância; se duas distâncias forem iguais, o ponto com o menor índice vem primeiro.
- Pegue os k primeiros pontos e conte seus rótulos.
- Retorne o rótulo com mais votos. Em caso de empate, retorne o rótulo cujo ponto mais próximo aparece primeiro na ordem.
Implemente knn_predict(points, labels, query, k).
Entrada
points: Os pontos de treinamento, cada um uma lista de coordenadas.
labels: O rótulo de cada ponto.
query: O ponto a classificar.
k: Quantos vizinhos votam.
Saída
Retorne o rótulo previsto.
Restrições
1 ≤ k ≤ número de pontos ≤ 1.000
1 ≤ dimensões ≤ 20
-1.000 ≤ cada coordenada ≤ 1.000
Exemplos
Entrada:
points = [
[1.0, 1.0],
[2.0, 2.0],
[8.0, 8.0],
[9.0, 9.0]
]
labels = ["A", "A", "B", "B"]
query = [3.0, 3.0]
k = 3
Saída esperada:
expected = "A"
Entrada:
std::vector<std::vector<double>> points = {
{1.0, 1.0},
{2.0, 2.0},
{8.0, 8.0},
{9.0, 9.0}
};
std::vector<std::string> labels = {"A", "A", "B", "B"};
std::vector<double> query = {3.0, 3.0};
long long k = 3;
Saída esperada:
std::string expected = "A";
Entrada:
double[][] points = new double[][] {
new double[] {1.0, 1.0},
new double[] {2.0, 2.0},
new double[] {8.0, 8.0},
new double[] {9.0, 9.0}
};
string[] labels = new string[] {"A", "A", "B", "B"};
double[] query = new double[] {3.0, 3.0};
long k = 3;
Saída esperada:
string expected = "A";
Explicação
Distâncias a partir de (3, 3): (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07. Os 3 rótulos mais próximos são A, A e B, então a resposta é A.
Entrada:
points = [
[0.0, 0.0],
[4.0, 0.0],
[0.0, 4.0],
[4.0, 4.0]
]
labels = ["red", "blue", "blue", "red"]
query = [1.0, 1.0]
k = 2
Saída esperada:
expected = "red"
Entrada:
std::vector<std::vector<double>> points = {
{0.0, 0.0},
{4.0, 0.0},
{0.0, 4.0},
{4.0, 4.0}
};
std::vector<std::string> labels = {"red", "blue", "blue", "red"};
std::vector<double> query = {1.0, 1.0};
long long k = 2;
Saída esperada:
std::string expected = "red";
Entrada:
double[][] points = new double[][] {
new double[] {0.0, 0.0},
new double[] {4.0, 0.0},
new double[] {0.0, 4.0},
new double[] {4.0, 4.0}
};
string[] labels = new string[] {"red", "blue", "blue", "red"};
double[] query = new double[] {1.0, 1.0};
long k = 2;
Saída esperada:
string expected = "red";
Explicação
O ponto mais próximo é (0, 0) (red); os dois seguintes, (4, 0) e (0, 4), estão à mesma distância, então vence o menor índice, (4, 0) (blue). Red e blue têm um voto cada, e o ponto de red veio primeiro, então a resposta é red.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Meça a distância euclidiana de cada ponto até a query e depois ordene os pontos pela distância, desempateando por menor índice.
Dica 2
Só os primeiros k pontos ordenados votam, então o rótulo final depende de um subconjunto pequeno do conjunto de treino.
Dica 3
Se houver empate nos votos, use o rótulo cujo ponto contribuinte mais próximo aparece primeiro na lista ordenada de vizinhos.
Complexidade esperada
tempo O(n log n), espaço extra O(n)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.