algorithm - 最小曼哈顿距离的算法

Question

我希望找到与一组点的曼哈顿距离/直线距离之和最小的点（即该点与集合中每个点之间的直线距离之和应该是最小的）。结果点可以是给定集合中的点之一（不一定）。如果存在多个具有相同最小距离的点，我希望检索所有这些点。

换句话说：

我有一个标有某些交叉点的​​网格。我想找到最接近所有标记的十字路口的十字路口。也就是说，我需要找到一个点，使得到所有点的距离之和最小。

Answer 1

曼哈顿距离最酷的地方在于距离本身由两个独立的分量组成：x 和 y 坐标上的距离。因此，您可以解决两个更简单的任务并将它们的结果合并以获得所需的结果。

我所说的任务是：给定的是一条线上的点。在直线上找到使到所有点的绝对距离之和最小的点。如果有很多找到所有这些（顺便说一句，它们总是变成一个易于证明的单个片段）。该段由集合的（可能两个）点中位数确定。中位数是指在其左侧和右侧具有相同数量的点的点。如果点的数量是偶数，则没有这样的点，并且您选择在两个方向上差异为 1 的点来形成线段。

在这里，我添加了这个更简单任务的解决方案示例：

如果线上的点是这样的：

-4 | | | 0 | 2 3 4
             ^

解决方案只是一个点，它就是2。

如果线上的点是这样的：

-4 | | | 0 | 2 3
         ^---^

整个段 [0, 2] 就是问题的解。

您分别为x和y坐标解决此任务，然后合并结果以获得最小距离点的矩形。

---

例子

现在是初始任务的解决方案示例。

想象一下，您想找到与集合的曼哈顿距离最小的点(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). 很明显，只要输入本身具有上述复杂性，就无法更快地解决任务。