algorithm - 找出数组中距零最远的两个元素之和

Question

给定一个数组，在该数组中找到离零最远的两个元素之和的最节省时间和空间的算法是什么？

编辑例如，[1, -1, 3, 6, -10] 最远的和等于 -11，等于 (-1)+(-10)。

Answer 1

使用锦标赛比较方法查找最大和第二大元素使用最少的比较，总共 n+log(n)-2。这样做两次，一次是为了找到最大和第二大的元素，比如 Z 和 Y，然后再次找到最小的和第二小的元素，比如 A 和 B。那么答案要么是Z+Y，要么是-A-B，所以再对比一下就解决了。总的来说，这需要 2n+2log(n)-3 比较。这仍然是 O(n)，但实际上比扫描整个列表 4 次以找到 A,B,Y,Z 更快(总共使用 4n-5 比较)。

在这两个教程中用图片和示例代码很好地解释了比赛方法:one和 two