ksdx 最近的时间轴更新 ksdx 最近的时间轴更新 |
ksdxV2EX 第 300456 号会员，加入于 2018-03-15 19:29:07 +08:00 |
ksdx 最近回复了
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 个数有重复……）。差不多了
Select Language