LC: 296. Best Meeting Point
https://leetcode.com/problems/best-meeting-point/
296. Best Meeting Point
Given an m x n binary grid grid where each 1 marks the home of one friend, return the minimal total travel distance.
The total travel distance is the sum of the distances between the houses of the friends and the meeting point.
The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.
Example 1:
Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 6
Explanation: Given three friends living at (0,0), (0,4), and (2,2).
The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal.
So return 6.Example 2:
Input: grid = [[1,1]]
Output: 1Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 200grid[i][j]is either0or1.There will be at least two friends in the
grid.
The Essence: Hier soll der Problemlöser die Lösungsstrategie vereinfacht verstehen: Es ist einfacher, wenn wir über diese Frage zuerst in 1D denken. Dabei kann man erkennen, dass der beste Meetingspunkt immer dem Median der Positionen der Personen entspricht. Man kann diese Tatsache in 2D übertragen, indem den Median in der y-Achse und x-Achse findet.
Details:
Es kann mathematisch bewiesen werden, dass der beste Treffpunkt bei dem Median und nicht bei dem Mittelwert liegt. Der Median kann als Maß verwendet werden, wenn den Extremwerten eine geringere Bedeutung beigemessen wird, typischerweise weil eine Verteilung schief ist.
Default Code:
Last updated