难度: Hard
Submission
运行时间: 36 ms
内存: 18.3 MB
class Solution:
def minTotalDistance(self, grid: List[List[int]]) -> int:
# Step 1: Find all friends' homes
homes = []
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
homes.append((i, j))
# Helper function to find the median of a list
def median(lst):
sorted_lst = sorted(lst)
length = len(sorted_lst)
if length % 2 == 0:
return (sorted_lst[length // 2 - 1] + sorted_lst[length // 2]) / 2
else:
return sorted_lst[length // 2]
# Step 2: Find the median x and y coordinates
x_coords = [home[0] for home in homes]
y_coords = [home[1] for home in homes]
median_x = median(x_coords)
median_y = median(y_coords)
# Step 3: Calculate the total distance to the median point
total_distance = 0
for home in homes:
x, y = home
total_distance += abs(x - median_x) + abs(y - median_y)
return total_distance
class Solution:
def minTotalDistance(self, grid: List[List[int]]) -> int:
# Step 1: Find all friends' homes and separate x and y coordinates
x_coords = []
y_coords = []
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
x_coords.append(i)
y_coords.append(j)
# Helper function to find the median of a list of integers
def int_median(lst):
sorted_lst = sorted(lst)
length = len(sorted_lst)
mid = length // 2
if length % 2 == 0:
return sorted_lst[mid - 1] # Take the lower of the two middle values for integer median
else:
return sorted_lst[mid]
# Step 2: Find the median x and y coordinates (as integers)
median_x = int_median(x_coords)
median_y = int_median(y_coords)
# Step 3: Calculate the total distance to the median point
total_distance = 0
for x, y in zip(x_coords, y_coords):
total_distance += abs(x - median_x) + abs(y - median_y)
return total_distance
Explain
这个题解的思路是利用中位数的性质来找到最佳的碰头地点。具体步骤如下： 1. 找出所有朋友的家的坐标，并将x坐标和y坐标分别存储在两个列表中。 2. 分别计算x坐标列表和y坐标列表的中位数，作为最佳碰头地点的坐标。 3. 计算所有朋友的家到最佳碰头地点的曼哈顿距离之和，即为最小的总距离。
时间复杂度: O(mn log(mn))
空间复杂度: O(mn)
class Solution:
def minTotalDistance(self, grid: List[List[int]]) -> int:
# Step 1: Find all friends' homes and separate x and y coordinates
x_coords = []
y_coords = []
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
x_coords.append(i)
y_coords.append(j)
# Helper function to find the median of a list of integers
def int_median(lst):
sorted_lst = sorted(lst)
length = len(sorted_lst)
mid = length // 2
if length % 2 == 0:
return sorted_lst[mid - 1] # Take the lower of the two middle values for integer median
else:
return sorted_lst[mid]
# Step 2: Find the median x and y coordinates (as integers)
median_x = int_median(x_coords)
median_y = int_median(y_coords)
# Step 3: Calculate the total distance to the median point
total_distance = 0
for x, y in zip(x_coords, y_coords):
total_distance += abs(x - median_x) + abs(y - median_y)
return total_distance
Explore
在计算中位数时选择返回下中位数（较小的中位数）而不是平均值，是因为在求解最小曼哈顿距离的问题中，中位数的位置确保了所有点到该点的距离之和最小。选择下中位数或上中位数对最终的总距离计算影响不大，因为在中位数附近的任何一个整数点，其总曼哈顿距离都非常接近。具体到选择下中位数，这是一个常见的约定，简化了实现，尤其是在整数索引的数组中更为直观。
曼哈顿距离是在格点系统（如城市街区）中，沿着格点线测量的距离，适合于网格状结构的地图上的距离计算。在本问题中，朋友的家和碰头点都是在一个网格上，且通常只能沿格线（即水平或垂直方向）移动。相比之下，欧几里得距离是直线距离，适用于可以自由移动的空间，不适合本题的格点限制。因此，对于网格布局，曼哈顿距离更能准确反映从一点到另一点的实际移动距离。
排序是计算中位数的一个关键步骤，其时间复杂度为O(n log n)。当朋友的数量非常多时，排序的操作确实会对性能有所影响。但是，这种影响是必要的，因为只有通过排序才能正确确定中位数的位置，从而计算出最小的曼哈顿距离。若考虑性能优化，可以探索使用线性时间的选择算法（如快速选择算法）来找中位数，以改善在极大数据量时的性能表现。
即使所有朋友的家位于网格的同一行或同一列，中位数的计算方法仍然适用。在这种情况下，中位数仍会是该行或该列的中心点，从而确保了计算出的曼哈顿距离是最小的。因此，中位数方法在处理这类边界条件时是有效的，可以正确地减少到碰头地点的总移动距离。