最佳的碰头地点。
有一队人（两人或以上）想要在一个地方碰面，他们希望能够最小化他们的总行走距离。
给你一个 2D 网格，其中各个格子内的值要么是 0，要么是 1。
1 表示某个人的家所处的位置。这里，我们将使用 曼哈顿距离 来计算，其中 distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|。
力扣296。
求行最优，求列最优。最优行和最优列确定一个点，这个点就是需要返回的值。
时间复杂度：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
}执行结果如下：
