LeetCode 296 Best Meeting Point

LeetCode

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: 1

Constraints:

m == grid.length n == grid[i].length
1 <= m, n <= 200 grid[i][j] is either 0 or 1.
There will be *at least two friends in the grid.

题目大意：

矩阵中1表示朋友的位置，求最佳见面位置，所有朋友到这个位置曼哈顿距离最短。

解题思路：

这是数学题也是非高频题。如果是一维，求最佳位置，是所有朋友位置的中点，也就是左边朋友和右边朋友的数量是一样。求距离也就是用相向双指针，求每对点的距离。
推广到二维，同理，x和y坐标是独立的。分别求距离即可。

解题步骤：

N/A

注意事项：

1. 用相向双指针，求每对点的距离

Python代码：

def minTotalDistance(self, grid: List[List[int]]) -> int:
	x_coordinates, y_coordinates = [], []
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			if grid[i][j] == 1:
				x_coordinates.append(i)
				y_coordinates.append(j)
	x_coordinates.sort()
	y_coordinates.sort()
	res = 0
	left, right = 0, len(y_coordinates) - 1
	while left < right:
		res += y_coordinates[right] - y_coordinates[left]
		left += 1
		right -= 1

	left, right = 0, len(x_coordinates) - 1
	while left < right:
		res += x_coordinates[right] - x_coordinates[left]
		left += 1
		right -= 1
	return res

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n), n为矩阵的长边大小