Условие
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.
Ограничения
1 ≤ k ≤ number of points ≤ 1,000
1 ≤ dimensions ≤ 20
-1,000 ≤ each coordinate ≤ 1,000
Примеры
Ввод:
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.
Ввод:
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. Следуйте условию и ограничениям выше.