Implement k-Nearest Neighbors
Problem statement
Implement k-nearest neighbors for labeled training points and query points.
For this exercise, assume a classification task with integer labels and squared Euclidean distance. For each query, choose the k training points ordered by increasing squared distance, breaking equal-distance ties by original training index. Return the most frequent selected label; break a vote tie by choosing the smallest label. Return one prediction per query, in query order.
Function
predictKnn(points: int[][], labels: int[], queries: int[][], k: int) → int[]Examples
Example 1
points = [[0],[2],[5]]labels = [1,2,2]queries = [[1],[4]]k = 1return = [1,2]For query 1, points 0 and 1 tie at squared distance 1, so index 0 wins and predicts label 1. For query 4, point 2 is nearest and predicts label 2.
Example 2
points = [[0],[2],[4],[6]]labels = [9,4,4,9]queries = [[3]]k = 4return = [4]All four points vote. Labels 4 and 9 each receive two votes, so the smaller label 4 wins.
Example 3
points = [[0,0],[0,0],[2,2]]labels = [7,3,3]queries = [[0,0]]k = 1return = [7]The first two points have distance zero. The smaller original index is selected, so the prediction is label 7.
Constraints
- 1 <= points.length <= 200.
- 0 <= queries.length <= 100.
- Every point and query has between 1 and 10 coordinates.
- All point and query vectors have the same number of coordinates.
- Every coordinate is between -10000 and 10000.
- labels.length equals points.length.
- Every label is between -1000000 and 1000000.
- 1 <= k <= points.length.