最小曼哈顿距离算法
我希望从一组点中找到曼哈顿距离/直线距离的总和最小的点（即，该点与集合中每个点之间的直线距离的总和应最小）。结果点可以是给定集合中的点之一（不一定）。如果存在多个具有相同最小距离的点，我希望检索所有这些点。
换一种说法：
我有一个带有某些交叉点的网格。我想找到最接近所有标记交点的交点。也就是说，我需要找到一个点，使得到所有点的距离之和最小。
回答：
关于Manhatan距离的最酷的事情是，距离本身包含两个独立的分量：x和y坐标上的距离。因此，您可以解决两个更简单的任务，并合并它们的结果以获得所需的结果。
我要说的任务是：给定直线上的点。在直线上找到使所有点的绝对距离之和最小的点。如果有很多找到它们的全部（顺便说一句，它们总是变成一个容易证明的单一部分）。该段由集合的（可能是两个）点中位数确定。中位数是指在左边和右边具有相等数量点的点。如果点的数量为奇数，则不存在这样的点，您可以选择两个方向上的差为1的点以形成线段。
在这里，我添加了此简单任务的解决方案示例：
如果线上的点是这样的：
-4 | | | 0 | 2 3 4 ^
解决方案只是一点，事实就是如此2。
如果线上的点是这样的：
-4 | | | 0 | 2 3 ^---^
整个段[0，2]是问题的解决方案。
您可以针对x和分别解决此任务y，然后合并结果以获得最小距离点的矩形。
例
现在来介绍初始任务的解决方案示例。
假设您要查找距集合的最小Manhatan距离的点 (0, 6), (1, 3), (3, 5), (3, 3), (4, 7), (2, 4)
您形成了两个简单的任务：
对于x：
0 1 2 3 3 4 ^-^
这是解决方案的问题[2, 3]（请注意，这里有重复的point 3，我可能不是最直观的方式表示）。
对于y：
3 3 4 5 6 7 ^-^
这里的解决方案是细分[4, 5]。
最后，我们得到初始任务的解决方案是带有公式的矩形：
2 <= x <= 3; 4 <= y <= 5复杂
由于许多人对此帖子表现出兴趣，因此我决定对其进行进一步的改进。
让我们谈谈复杂性。
任务的复杂性实际上与解决较简单的任务的复杂度相同（因为如前所述，解决方案实际上包括解决两个较简单的任务）。许多人会通过排序然后选择中位数来解决它。但是，这将导致O(nlog
n)复杂性，即n输入集中的点数在哪里。
如果使用更好的算法来找到第k个元素，则可以改进此方法（C ++
STL中的实现示例）。该算法基本上遵循与qsort相同的方法。运行时间为O(n)。即使在两个中点的情况下，它仍将保持线性（需要运行同一算法两次），因此该算法的总复杂度变为O(n)。显然，只要输入本身具有上述复杂性，就无法更快地完成任务。
以上是 最小曼哈顿距离算法 的全部内容， 来源链接： utcz.com/qa/435280.html
