Tous les défis
Moyen 1 résolu 100.0 % de réussite

K-Nearest Neighbors Classifier

Predict a label by majority vote of the k closest training points.

Ce que vous allez apprendre

  • Find the closest training points
  • Predict by majority vote
  • Break ties deterministically

Problème

Afficher la traduction

K-nearest neighbors (KNN) classifies a new point by looking at the k training points closest to it and taking the most common label.

  1. Compute the Euclidean distance from query to every point.
  2. Sort the points by distance; if two distances are equal, the point with the smaller index comes first.
  3. Take the first k points and count their labels.
  4. 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.

Contraintes

1 ≤ k ≤ number of points ≤ 1,000

1 ≤ dimensions ≤ 20

-1,000 ≤ each coordinate ≤ 1,000

Exemples

Exemple 1
Entrée :
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

Sortie attendue :
expected = "A"
Entrée :
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;

Sortie attendue :
std::string expected = "A";
Entrée :
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;

Sortie attendue :
string expected = "A";

Explication

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.

Exemple 2
Entrée :
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

Sortie attendue :
expected = "red"
Entrée :
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;

Sortie attendue :
std::string expected = "red";
Entrée :
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;

Sortie attendue :
string expected = "red";

Explication

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.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Measure each point’s Euclidean distance to the query, then rank points by distance with smaller indices breaking ties.

Indice 2

Only the first k sorted points vote, so the final label depends on a tiny subset of the training set.

Indice 3

If vote counts tie, use the label whose nearest contributing point appears earliest in the sorted neighbor list.

Complexité attendue

O(n log n) time, O(n) extra space

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 930 ms - 5/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.