Problema
K-nearest neighbors (KNN) classifies a new point by looking at the k training points closest to it and taking the most common label.
- Compute the Euclidean distance from
queryto every point. - Sort the points by distance; if two distances are equal, the point with the smaller index comes first.
- Take the first k points and count their labels.
- Return the label with the most votes. If labels tie, return the tied label whose closest point comes first in the sorted order.
Implement knn_predict(points, labels, query, k).
Input
points: The training points, each a list of coordinates.
labels: The label of each point.
query: The point to classify.
k: How many neighbors vote.
Output
Return the predicted label.
Restricciones
1 ≤ k ≤ number of points ≤ 1,000
1 ≤ dimensions ≤ 20
-1,000 ≤ each coordinate ≤ 1,000
Ejemplos
Entrada:
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]
]
Salida esperada:
expected = "A"Entrada:
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}
};
Salida esperada:
std::string expected = "A";Entrada:
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}
};
Salida esperada:
string expected = "A";Explicación
Distances from (3, 3): (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07. The 3 nearest labels are A, A and B, so the answer is A.
Entrada:
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]
]
Salida esperada:
expected = "red"Entrada:
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}
};
Salida esperada:
std::string expected = "red";Entrada:
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}
};
Salida esperada:
string expected = "red";Explicación
The nearest point is (0, 0) (red); the next two, (4, 0) and (0, 4), are at the same distance, so the smaller index (4, 0) (blue) wins the tie. Red and blue have one vote each, and red's point came first, so the answer is red.
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.