我希望能够找到与曼哈顿距离/直线距离的最小总和的点从一组点（即这点和每个点的集合之间的直线距离的总和应该是最小）。所得点可以从给定的一组（不是必须的）的点中的一个。如果用相同的最短距离存在不止一个点，我想找回所有的人。

I wish to find the point with the minimum sum of manhattan distance/rectilinear distance from a set of points (i.e the sum of rectilinear distance between this point and each point in the set should be minimum ). The resulting point can be one of the points from the given set (not necessarily). In case more than one points exist with the same minimum distance, i wish to retrieve all of them.

换句话说：

我有一定的交叉点网格标记。我想找到最接近的所有标记的​​交叉点的交叉点。也就是说，我需要找到一个点，使得距离的所有点的总和最小。

I have a grid with certain intersections marked. I'd like to find the intersection that is closest to all the marked intersections. That is, I need to find a point such that the sum of distances from all points is minimum.

推荐答案

有关曼哈坦距离很酷的事情是，距离本身包括两个独立部分组成：距离x和y坐标。因此，可以解决两个简单的任务和合并的结果，从它们来获得所需的结果。

The cool thing about the Manhatan distance is that the distance itself comprises of two independent components: the distance on the x and y coordinate. Thus you can solve two simpler tasks and merge the results from them to obtain the desired results.

我说的是任务：给定的是一个线上的点。找到最小化绝对距离之和的所有点的线的点。如果有很多发现它们全部（顺便说一句，他们总是变成为单个段这是很容易证明）。段是由（潜在2）测定点的集合中位数。由中间我的意思是具有相等数量的点的左侧和到它的右侧的点。万一点的数目是奇数不存在这样的点，并选择与差1分在两个方向上，以形成线段。

The task I speak of is: given are points on a line. Find the point on the line that minimizes the sum of the absolute distances to all the points. If there are many find all of them (btw they always turn to be a single segment which is easy to prove). The segment is determined by the (potentially two) points medians of the set. By median I mean the point that has equal number of points to the left and to the right of it. In case the number of points is odd there is no such point and you choose the points with difference 1 in both directions to form the segment.

在这里，我补充这个简单的任务解决方案的例子：

Here I add examples of solutions of this simpler task:

在案件上线的点是这样的：

In case the points on the line are like that:

-4 | | | 0 | 2 3 4
             ^

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

在案件上线的点是这样的：

In case the points on the line are like that:

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

整段[0,2]是该问题的解决方案。

The whole segment [0, 2] is the solution of the problem.

您单独解决这个任务的 X 和是的坐标，然后将结果合并取得的矩形最低疏远点。

You solve this task separately for the x and y coordinate and then merge the results to obtain the rectangle of minimum distanced points.

现在来作初始任务的解决方案的一个例子

And now comes an example of the solution for the initial task.

想象一下，你想找到的最小曼哈坦距离设定（0,6），（1,3），（3,5），（3,3），（点4，7），（2,4）

Imagine you want to find the points that are with minimum Manhatan distance to the set (0, 6), (1, 3), (3, 5), (3, 3), (4, 7), (2, 4)

您形成两个简单的任务：

You form the two simpler tasks:

有关X：

0 1 2 3 3 4
    ^-^

和这里的解决方案是段 [2，3] （注意，这里我们有重复点 3 ，这是我重新psented中可能不是最直观的方式$ P $）。

And here the solution is the segment [2, 3] (note that here we have duplicated point 3, which I represented in probably not the most intuitive way).

有关Y：

3 3 4 5 6 7
    ^-^

下面的解决方案是段 [4,5] 。

最后，我们得到的初始任务的解决方案是与式矩形

Finally we get that the solution of the initial task is the rectangle with formula:

 2 <= x <= 3; 4 <= y <= 5 

复杂

由于许多人表现出在这个岗位，我决定来改善它多一点的兴趣。

COMPLEXITY

As many people show interest in this post I decided to improve it a bit more.

让我们来谈谈复杂性。

该任务的复杂性其实是一样的解决简单的任务（因为前面已经讨论过的解决方案实际上包含求解两个简单的任务）的复杂性。很多人会去，并通过整理，然后选择出的中位数解决它。然而，这将导致 O（n日志N）的复杂性，其中 N 是一个点的输入设置的数字。

The complexity of the task is actually the same as the complexity of solving the simpler task (because as already discussed the solution actually consists of solving two simpler tasks). Many people will go and solve it via sorting and then choosing out the medians. However, this will cause O(nlog n) complexity, where n is the number of points in the input set.

如果用于求出第k个元素更好的算法被使用（实施例中实施这可以提高在C ++ STL）。该算法基本上遵循相同的方法的qsort。运行时间为 O（N）。即使是在两个位点的情况下，这将仍保持线性（需要相同的算法的两个运行），因此该算法的总复杂度变 O（n）的。很明显，该任务不能得到解决任何更快，只要输入本身是所提到的复杂度。

This can be improved if a better algorithm for finding the kth element is used (Example of implementation in the C++ STL). This algorithm basically follows the same approach as qsort. The running time is O(n). Even in the case of two median points this will still remain linear (needing two runs of the same algorithm), and thus the total complexity of the algorithm becomes O(n). It is obvious that the task can not be solved any faster, as long as the input itself is of the mentioned complexity.