Best Meeting Point,LeetCode,296

LeetCode 296题是关于寻找最佳会议地点的问题，题目描述如下：

题目描述： 给定一个 m x n 的二维网格 grid，每个格子 (i, j) 上都有一群人。我们需要找到一个点 (x, y) 作为会议地点，使得所有人到这个点的曼哈顿距离之和最小。

曼哈顿距离定义为：|i - x| + |j - y|。

示例：

输入: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]] 输出: 6 解释: 最优的会议地点是 (2, 2)，所有人到这个点的曼哈顿距离之和为 6。

解题思路

这个问题可以通过中位数来解决。具体思路如下：

1. 理解曼哈顿距离：
   • 曼哈顿距离是网格中两点之间的距离，计算方式为 |i - x| + |j - y|。
2. 分离维度：
   • 我们可以将问题分解为两个独立的维度：行和列。分别计算最优的行和列。
3. 中位数最小化：
   • 对于一维数组，中位数是最小化绝对值和的点。因此，我们可以分别计算行和列的中位数。

具体步骤

1. 收集所有点的行和列信息：
   • 遍历网格，记录每个点的行和列信息，并按权重（人数）累加。
2. 找到行和列的中位数：
   • 对行和列的累加数组分别找到中位数。
3. 计算总距离：
   • 使用找到的中位数行和列，计算所有人到这个点的曼哈顿距离之和。

代码实现

class Solution: def minTotalDistance(self, grid: List[List[int]]) -> int: if not grid or not grid[0]: return 0

    m, n = len(grid), len(grid[0])

    # 收集所有点的行和列信息
    rows, cols = [], []
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                rows.append(i)
                cols.append(j)

    # 行的中位数
    rows.sort()
    row_median = rows[len(rows) // 2]

    # 列的中位数
    cols.sort()
    col_median = cols[len(cols) // 2]

    # 计算总距离
    distance = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                distance += abs(i - row_median) + abs(j - col_median)

    return distance

解释

1. 收集信息：
   • 遍历网格，将所有有人（值为1）的行和列分别存储到 rows 和 cols 列表中。
2. 排序找中位数：
   • 对 rows 和 cols 列表进行排序，然后找到中位数。中位数是最小化绝对值和的点。
3. 计算距离：
   • 遍历网格，计算每个有人点到中位数点的曼哈顿距离之和。

复杂度分析

• 时间复杂度：O(m n + k log(k))，其中 k 是网格中人的总数。主要耗时在排序上。
• 空间复杂度：O(k)，用于存储行和列信息。

这种方法利用了中位数的性质，有效地解决了问题。希望这个解释对你理解这道题有所帮助！如果有更多问题，欢迎继续提问。