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编写。代码如下：
代码语言：go复制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代码
