关于Manhatan距离的最酷的事情是,距离本身包含两个独立的分量:x和y坐标上的距离。因此,您可以解决两个更简单的任务,并合并它们的结果以获得所需的结果。
我要说的任务是:给定直线上的点。在直线上找到使所有点的绝对距离之和最小的点。如果有很多找到它们的全部(顺便说一句,它们总是变成一个容易证明的单一部分)。该段由集合的(可能是两个)点中位数确定。中位数是指在左边和右边具有相等数量点的点。如果点的数量为奇数,则不存在这样的点,您可以选择两个方向上的差为1的点以形成线段。
如果线上的点是这样的:
-4 | | | 0 | 2 3 4
^
解决方案只是一点,事实就是如此2
。
如果线上的点是这样的:
-4 | | | 0 | 2 3
^---^
整个段[0,2]是问题的解决方案。
您可以针对x
和分别解决此任务y
,然后合并结果以获得最小距离点的矩形。