One-Nearest-Neighbor Classification with Manhattan Distance
Problem statement
You are given a nonempty set of labeled training samples and a set of query samples. Each sample is an integer feature vector.
For every query, find the single training sample with the smallest Manhattan distance:
distance(a, b) = sum(abs(a[i] - b[i]))
If several training samples have the same minimum distance, choose the one that appears earliest in trainingFeatures.
Return the chosen training label for every query, in query order.
Function
classifyOneNearestNeighborManhattan(trainingFeatures: int[][], trainingLabels: int[], queries: int[][]) → int[]Examples
Example 1
trainingFeatures = [[0,0],[3,0],[2,3]]trainingLabels = [10,20,30]queries = [[2,1],[2,3]]return = [20,30]The first query is two units from both the first and second rows, so the earlier of those tied nearest rows supplies label 20 only after checking all distances: its distances are 3, 2, and 2, making the second row the earliest minimum. The second query exactly matches the third row.
Example 2
trainingFeatures = [[-2,1],[2,1]]trainingLabels = [7,9]queries = [[0,1],[3,2]]return = [7,9]The first query ties at Manhattan distance two and selects the earlier row; the second is closest to [2,1].
Constraints
1 <= trainingFeatures.length == trainingLabels.length <= 2000.1 <= queries.length <= 2000.1 <= trainingFeatures[i].length == queries[j].length <= 100.-10^4 <= trainingFeatures[i][k], queries[j][k] <= 10^4.- Every Manhattan-distance sum fits in a signed 64-bit integer.