Skip to content

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


回到顶部