Tutte le sfide
Media 1 risolta 100.0% di accettazione

K-Nearest Neighbors Classifier

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

Cosa imparerai

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

Problema

Mostra traduzione

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.

Vincoli

1 ≤ k ≤ number of points ≤ 1,000

1 ≤ dimensions ≤ 20

-1,000 ≤ each coordinate ≤ 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

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.

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

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.

Come affrontarlo

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

Suggerimento 1

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

Suggerimento 2

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

Suggerimento 3

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

Complessità attesa

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

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.