Skip to content

Latest commit

 

History

History

296.Best-Meeting-Point

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

296.Best-Meeting-Point

本题的笨方法,就是存下所有persons的位置,然后遍历每个点,计算该点到所有person的曼哈顿距离之后。时间复杂度是o(MNK).

比较聪明的办法就是利用数学的性质。对于任意的序列x1,x2,x3,...,xn,我们要找到其中的一个k,使得

min_{k} |xi-k| for i=1,2,..,n

利用求导(非连续函数的特殊求导定义)的方法,可以得到如下的结论,最优的k是这个数列的中位数,注意不是平均数。如果序列里面有偶数个,那么中位数就是中间两个数的平均值。

在本题里,最优点坐标的X可以直接判定是所有persons横坐标的中位数,Y就是所有persons纵坐标的中位数。知道了(X,Y)就可以直接计算所有人到该点的曼哈顿距离。

Leetcode Link