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代码

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