algorithm - O(nlogn) 算法最小化 abs(x+y)

Question

我在最近的一次采访中被问到一个问题。我无法解决这个问题。对算法设计感兴趣的人可能会喜欢这个问题。

给定一个实数数组 S，在 S 中找到一对使 |x+y| 最小的数字 x&y。同样的算法应该设计为在 O(nlogn) 中运行。

我找不到解决这个问题的方法。谁能指导我朝着正确的方向解决这个问题？任何建议将不胜感激。

Answer 1

对数字进行排序。对每个元素 x 进行二分查找 -x。您得到最接近的数字 y 以最小化 |x+y|。

注意:您还可以优化第二部分。从第一个和最后一个元素的索引开始:i=0，j=n-1。在每次迭代中计算和，更新最小和，如果 sum<0 则递增 i 或递减 j(当 sum>=0 时)。