296._Best_Meeting_Point.md

296. Best Meeting Point

题目： https://leetcode.com/problems/best-meeting-point/

难度 : Hard

思路：

提示是先从一维开始，其实一开始是略迷茫的，因为如果两个点，那么只要在这两个之间，一定就是最小值，线段长度。

不过倘若点增加到三个，那么就是第三个点处。

然后发现了一个很棒的stackoverflow page

http://stackoverflow.com/questions/10402087/algorithm-for-minimum-manhattan-distance

因为一开始理解错误二维数组的输入，以为是给的locs这样的数组，所以直接这样写了，然后发现给的是格子，所以但是还是偷懒这样写了。

AC 代码

class Solution(object):
    def minTotalDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        res = 0
        locs = []

        m = len(grid)
        n = len(grid[0]) if m else 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    locs.append([i,j])


        locs.sort(key = lambda point: point[0])
        x = locs[len(locs)/2][0]
        for point in locs:
        	res += abs(point[0] - x)

        locs.sort(key = lambda point: point[1])
        y = locs[len(locs)/2][1]
        for point in locs:
        	res += abs(point[1] - y)

        return res