[数据结构与算法]2022-02-03：有一队人（两人或以上）想要在一个地方碰面，他们希望能够最小化他们的总行走距离。 给你一个 2D 网格，其中各个格子内的值要么是 0，要么是

2022-02-03：最佳的碰头地点。
有一队人（两人或以上）想要在一个地方碰面，他们希望能够最小化他们的总行走距离。
给你一个 2D 网格，其中各个格子内的值要么是 0，要么是 1。
1 表示某个人的家所处的位置。这里，我们将使用 曼哈顿距离 来计算，其中 distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|。
力扣296。

答案2022-02-03：

求行最优，求列最优。最优行和最优列确定一个点，这个点就是需要返回的值。
时间复杂度：O(N^2)。
空间复杂度：O(N)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    grid := [][]int{
        {1, 0, 0, 0, 1},
        {0, 0, 0, 0, 0},
        {0, 0, 1, 0, 0},
    }
    ret := minTotalDistance(grid)
    fmt.Println(ret)
}

func minTotalDistance(grid [][]int) int {
    N := len(grid)
    M := len(grid[0])
    iOnes := make([]int, N)
    jOnes := make([]int, M)
    for i := 0; i < N; i++ {
        for j := 0; j < M; j++ {
            if grid[i][j] == 1 {
                iOnes[i]++
                jOnes[j]++
            }
        }
    }
    total := 0
    i := 0
    j := N - 1
    iRest := 0
    jRest := 0
    for i < j {
        if iOnes[i]+iRest <= iOnes[j]+jRest {
            total += iOnes[i] + iRest
            iRest += iOnes[i]
            i++
        } else {
            total += iOnes[j] + jRest
            jRest += iOnes[j]
            j--
        }
    }
    i = 0
    j = M - 1
    iRest = 0
    jRest = 0
    for i < j {
        if jOnes[i]+iRest <= jOnes[j]+jRest {
            total += jOnes[i] + iRest
            iRest += jOnes[i]
            i++
        } else {
            total += jOnes[j] + jRest
            jRest += jOnes[j]
            j--
        }
    }
    return total
}

执行结果如下：

左神java代码