296 Best Meeting Point
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
