V2EX › ksdx 的所有回复 › 第 1 页 / 共 1 页

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

2018-03-28 22:43:37 +08:00

回复了 fov6363 创建的主题 › 程序员 › [面试][算法] 昨天面试碰到了一个算法题,比较有难度,放上来看各位 v 友有没有办法和思路?

也可以用物理的方式理解，假设数轴是在一个平面上，每个点都打个洞，用线挂一个等重小球，穿过这个洞。然后到 n 个点距离和最短就等于是把这 n 条线打结在一个点上，然后由于小球重力，会在某个位置平衡，这是小球总的势能降到最低（水往低处流，能量最小~）。势能最小也意味着在平面上的线长度和最小，平面下的线长度和最长。由于是数轴，所以只要考虑左右平衡，左右小球数量相等，那么就会达到平衡，考虑下奇偶数。（类似三角形费马点）
这个也可以扩展到，平面、空间里。

2018-03-28 22:34:31 +08:00

回复了 fov6363 创建的主题 › 程序员 › [面试][算法] 昨天面试碰到了一个算法题,比较有难度,放上来看各位 v 友有没有办法和思路?

这个应该就是求解，数轴上到任意 n 个点的距离和最短吧，如果不限制是正整数的话，那么这个点（对应具体数值）在中间位置就可以（左右点数量相等，要考虑 n 为奇偶数，要考虑 n 个数有重复……）。差不多了