【Google】 面经， 这题怎么搞？

N*N的矩阵，M个朋友随机住在矩阵上，求聚会地点，满足所有朋友总路程最短, lg复
杂度


-----
1. 弄一个 n * n 的matrix.
2. 在 M个朋友走一遍BFS, 矩阵中 走过 单元+ 1
3. 求单元中间的低得数

不知道还有没有更优的算法？

Lc 原题 shortest building  我也只知道bfs解法 log的复杂度 有点懵逼

找所有朋友坐标的中位数即可。坐标中位数的意思是x是所有x中位数，y是所有y中位数。总复杂度O(n)

N维空间的距离之和 求中位数的那个应该是仅限于距离按照曼哈顿距离计算的时候才使用 （not sure）

题库原题

聚会一定在朋友家吗？

2011051305 发表于 2017-8-1 09:49
N维空间的距离之和 求中位数的那个应该是仅限于距离按照曼哈顿距离计算的时候才使用 （not sure）

lz这道面经题就是只能横竖走的，

brn 发表于 2017-8-1 13:45
曼哈顿距离： 求中位数 O(N)
欧几里得距离：求均值 O(N)

恩 如果以曼哈顿距离求算点到点的距离，那么就可以采用中位数的方法达到O(n)

但是我也不知道O（logn)怎么能得到，他不是说朋友是随机的么，这样我无论如何也不能通过二分得到更小的范围啊？