문제
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
예시
입력:
k = 3
query = [3.0, 3.0]
labels = ["A", "A", "B", "B"]
points = [
[1.0, 1.0],
[2.0, 2.0],
[8.0, 8.0],
[9.0, 9.0]
]
예상 출력:
expected = "A"입력:
long long k = 3;
std::vector<double> query = {3.0, 3.0};
std::vector<std::string> labels = {"A", "A", "B", "B"};
std::vector<std::vector<double>> points = {
{1.0, 1.0},
{2.0, 2.0},
{8.0, 8.0},
{9.0, 9.0}
};
예상 출력:
std::string expected = "A";입력:
long k = 3;
double[] query = new double[] {3.0, 3.0};
string[] labels = new string[] {"A", "A", "B", "B"};
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 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.
입력:
k = 2
query = [1.0, 1.0]
labels = ["red", "blue", "blue", "red"]
points = [
[0.0, 0.0],
[4.0, 0.0],
[0.0, 4.0],
[4.0, 4.0]
]
예상 출력:
expected = "red"입력:
long long k = 2;
std::vector<double> query = {1.0, 1.0};
std::vector<std::string> labels = {"red", "blue", "blue", "red"};
std::vector<std::vector<double>> points = {
{0.0, 0.0},
{4.0, 0.0},
{0.0, 4.0},
{4.0, 4.0}
};
예상 출력:
std::string expected = "red";입력:
long k = 2;
double[] query = new double[] {1.0, 1.0};
string[] labels = new string[] {"red", "blue", "blue", "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 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.
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.