Best Meeting Point

要点：

• 题本身不难理解，manhattan distance。follow up就变成weighted了（因为一个地方可以有多个住户）
• 注意input是grid的形式，一种方法是2d iterate，然后用两个数组分别存x，y，只需要对column sort，row是按顺序的iterate的。最后直接取中
• 这题之所以是Hard，因为有另一种方法：不用sort，不用找median，类似于nested weighted sum II，只不过变成双向而非单向
  • 假设到某一点i和j分别对应左右的某点（注意，和另一边无关），left表示所有i左边的人，right表示所有j右边的人。如果i右移，j左移，每移动一步所有当前left，right的距离d都会增加1。显然，在每一步选最小的增加距离最合算（到目前为止，不同层总的增加数是不同的）。而如果当前i/j上有人，人口也会增加（即left/right增加）。
  • 为什么是i<j？当i==j的时候，这个位置的新增人（either left or right）距离都是0，所以不需要计入距离。推广到一般的过程，所有新增人口，都不会对当前轮的d有影响。所以要d+=left/right是上一轮的
  • 另外，也利用了each row/col的sum，i.e.，把行列浓缩成一个值来降维。
  • 显然，这个方法也可以处理weighted的情况。所以time complexity: O(mn)

错误点：

• 最后结果不是/2

# 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?# Hide Company Tags Twitter# Hide Tags Math Sort# Hide Similar Problems (H) Shortest Distance from All Buildingsclass Solution(object):    def minTotalDistance(self, grid):        """        :type grid: List[List[int]]        :rtype: int        """        row_num = [sum(row) for row in grid]        col_num = [sum(col) for col in zip(*grid)]        def minDist(sum_list):            l, r = -1, len(sum_list)            left,right=0,0            d=0            while l