Đề bài
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.
Ràng buộc
1 ≤ k ≤ number of points ≤ 1,000
1 ≤ dimensions ≤ 20
-1,000 ≤ each coordinate ≤ 1,000
Ví dụ
Đầu vào:
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
Kết quả mong đợi:
expected = "A"
Đầu vào:
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;
Kết quả mong đợi:
std::string expected = "A";
Đầu vào:
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;
Kết quả mong đợi:
string expected = "A";
Giải thích
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.
Đầu vào:
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
Kết quả mong đợi:
expected = "red"
Đầu vào:
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;
Kết quả mong đợi:
std::string expected = "red";
Đầu vào:
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;
Kết quả mong đợi:
string expected = "red";
Giải thích
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.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Measure each point’s Euclidean distance to the query, then rank points by distance with smaller indices breaking ties.
Gợi ý 2
Only the first k sorted points vote, so the final label depends on a tiny subset of the training set.
Gợi ý 3
If vote counts tie, use the label whose nearest contributing point appears earliest in the sorted neighbor list.
Độ phức tạp mong đợi
O(n log n) time, O(n) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.