Все задачи
Средне Решена: 1 Процент решений: 100.0%

K-Nearest Neighbors Classifier

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

Чему вы научитесь

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

Условие

Показать перевод

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.

Ограничения

1 ≤ k ≤ number of points ≤ 1,000

1 ≤ dimensions ≤ 20

-1,000 ≤ each coordinate ≤ 1,000

Примеры

Пример 1
Ввод:
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

Ожидаемый вывод:
expected = "A"
Ввод:
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;

Ожидаемый вывод:
std::string expected = "A";
Ввод:
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;

Ожидаемый вывод:
string expected = "A";

Пояснение

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.

Пример 2
Ввод:
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

Ожидаемый вывод:
expected = "red"
Ввод:
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;

Ожидаемый вывод:
std::string expected = "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}
};
string[] labels = new string[] {"red", "blue", "blue", "red"};
double[] query = new double[] {1.0, 1.0};
long k = 2;

Ожидаемый вывод:
string expected = "red";

Пояснение

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.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Ожидаемая сложность

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

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

# Участник Язык Время Память Оценка ИИ Решение
1 ННикита Python 930 ms - 5/5 Посмотреть код

Учитесь у других

Решения сообщества

Внимание, спойлер: ниже 1 полное решение Попробуйте сначала решить сами. Вы всегда можете посмотреть код других и AI-обзоры. Войдите и решите задание, чтобы присоединиться к обсуждению.