Problema
Il k-nearest neighbors (KNN) classifica un nuovo punto guardando i k punti di addestramento più vicini e prendendo l'etichetta più comune.
- Calcola la distanza euclidea da
querya ogni punto. - Ordina i punti per distanza; se due distanze sono uguali, viene prima il punto con l'indice minore.
- Prendi i primi k punti e conta le loro etichette.
- 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
Input:
k = 3
query = [3.0, 3.0]
labels = ["A", "A", "B", "B"]
points = [
[1.0, 1.0],
[2.0, 2.0],
[8.0, 8.0],
[9.0, 9.0]
]
Output atteso:
expected = "A"Input:
long long k = 3;
std::vector<double> query = {3.0, 3.0};
std::vector<std::string> labels = {"A", "A", "B", "B"};
std::vector<std::vector<double>> points = {
{1.0, 1.0},
{2.0, 2.0},
{8.0, 8.0},
{9.0, 9.0}
};
Output atteso:
std::string expected = "A";Input:
long k = 3;
double[] query = new double[] {3.0, 3.0};
string[] labels = new string[] {"A", "A", "B", "B"};
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}
};
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.
Input:
k = 2
query = [1.0, 1.0]
labels = ["red", "blue", "blue", "red"]
points = [
[0.0, 0.0],
[4.0, 0.0],
[0.0, 4.0],
[4.0, 4.0]
]
Output atteso:
expected = "red"Input:
long long k = 2;
std::vector<double> query = {1.0, 1.0};
std::vector<std::string> labels = {"red", "blue", "blue", "red"};
std::vector<std::vector<double>> points = {
{0.0, 0.0},
{4.0, 0.0},
{0.0, 4.0},
{4.0, 4.0}
};
Output atteso:
std::string expected = "red";Input:
long k = 2;
double[] query = new double[] {1.0, 1.0};
string[] labels = new string[] {"red", "blue", "blue", "red"};
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}
};
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.
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.