Tutte le sfide
Media 1 risolta 100.0% di accettazione

Classificatore k-nearest neighbors

Prevedi un'etichetta con il voto di maggioranza dei k punti di addestramento più vicini.

Cosa imparerai

  • Trovare i punti di addestramento più vicini
  • Prevedere con un voto a maggioranza
  • Risolvere i pareggi in modo deterministico

Problema

Il k-nearest neighbors (KNN) classifica un nuovo punto guardando i k punti di addestramento più vicini e prendendo l'etichetta più comune.

  1. Calcola la distanza euclidea da query a ogni punto.
  2. Ordina i punti per distanza; se due distanze sono uguali, viene prima il punto con l'indice minore.
  3. Prendi i primi k punti e conta le loro etichette.
  4. Restituisci l'etichetta con più voti. In caso di parità, restituisci l'etichetta il cui punto più vicino compare per primo nell'ordine.

Implementa knn_predict(points, labels, query, k).

Input

points: I punti di addestramento, ognuno una lista di coordinate.

labels: L'etichetta di ogni punto.

query: Il punto da classificare.

k: Quanti vicini votano.

Output

Restituisci l'etichetta prevista.

Vincoli

1 ≤ k ≤ numero di punti ≤ 1.000

1 ≤ dimensioni ≤ 20

-1.000 ≤ ogni coordinata ≤ 1.000

Esempi

Esempio 1
Input:
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

Output atteso:
expected = "A"
Input:
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;

Output atteso:
std::string expected = "A";
Input:
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;

Output atteso:
string expected = "A";

Spiegazione

Distanze da (3, 3): (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07. Le 3 etichette più vicine sono A, A e B, quindi la risposta è A.

Esempio 2
Input:
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

Output atteso:
expected = "red"
Input:
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;

Output atteso:
std::string expected = "red";
Input:
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;

Output atteso:
string expected = "red";

Spiegazione

Il punto più vicino è (0, 0) (red); i due successivi, (4, 0) e (0, 4), sono alla stessa distanza, quindi vince l'indice minore, (4, 0) (blue). Red e blue hanno un voto ciascuno, e il punto di red è arrivato per primo, quindi la risposta è red.

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Misura la distanza euclidea di ogni punto dalla query, poi ordina i punti per distanza rompendo i pari indice più piccolo.

Suggerimento 2

Votano solo i primi k punti ordinati, quindi l’etichetta finale dipende da una piccola parte del training set.

Suggerimento 3

Se i conteggi dei voti sono pari, usa l’etichetta il cui punto contributivo più vicino appare per primo nella lista ordinata dei vicini.

Complessità attesa

tempo O(n log n), spazio aggiuntivo O(n)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

# Programmatore Linguaggio Tempo Memoria Voto dell'IA Soluzione
1 ННикита Python 930 ms - 5/5 Vedi il codice

Impara dagli altri

Soluzioni della community

Attenzione spoiler: 1 soluzione completa sotto Prova prima a risolverla da solo. Puoi comunque sbirciare il codice degli altri sviluppatori e le recensioni AI. Accedi e risolvi la sfida per partecipare alla discussione.