Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Feb. 12, 2018 -
[[1, 2,] [4, 3] [6, 3]]
find a point which minimizes the sum of the manhattan distance to each point
dist = abs(x1 - x2) + abs(y1 - y2)
xs = [1, 4, 6]
ys = [2, 3, 3]
quickselect
medianX 4, medianY 3
O(n)
Math.abs(x - x1)
(x1 + x2 +.. + xn)/ n -> median - 1, 2, 3, 2 , 1, 2, 3, 4 - 2 + 3/ 2
[4,2,3,1]
https://en.wikipedia.org/wiki/Quickselect
QuickSelect(xs, 1) // average case: O(n)
-----------------------------
(X:7) 4, 6, 8
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment