Meeting Point

题目描述

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0), (0,4), and (2,2):

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

Hint:

Try to solve it in one dimension first. How can this solution apply to the two dimension case?

follow up:

There can be multiple people in the same room.

解题方法

这一题距离的计算方法其实是x于y分开的，所以我们可以把它分为2个1-D的结果的和。

在X轴的1-D问题上，最佳的meeting point就是所有X坐标的median中间点

  • 如果是偶数个，只要是中间两个点之间就可以
  • 如果是奇数个，那就应该是中间那个点

Solution

class Solution(object):
    def minTotalDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid:
            return 0

        row = len(grid)
        col = len(grid[0])

        rowArr = []
        colArr = []

        for i in range(row):
            for j in range(col):
                if grid[i][j] == 1:
                   rowArr.append(i)
                   colArr.append(j)
        colArr.sort()

        result = 0
        medianRow = rowArr[len(rowArr)/2]
        medianCol = colArr[len(colArr)/2]

        for r in rowArr:
            result += abs(r-medianRow)
        for c in colArr:
            result += abs(c-medianCol)

        return result

Reference