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 或递减 j（当 sum>=0），则增加 i。

Answer 2

面试官的问题 - 或您的重述 - 似乎缺乏两个方面。

1）实数非常非常难以在计算机中表示。它们可以用符号格式表示，也可以表示为浮点数的子集，以及实数的子集（如整数）

2) Mod 有两个参数，它们的声明是最小化 mod(x+y) 而不是 mod(x,y)。

这可能是一个旨在挑战问题陈述错误的面试问题吗？

维基百科将“mod”定义为“给定两个正数，a（被除数）和 n（除数），模 n（缩写为 mod n）是 a 除以 n 的欧几里得除法的余数。” 和“欧几里得除法”作为“在算术中，欧几里得除法是两个整数相除产生商和余数的常规过程。”

更多关于实数的“mod”没有意义：http ://www.abstractmath.org/MM/MMNumberTheory.htm

如果问题被定义为在 O(nlogn) 中最小化 mod(x,y) 的整数数组，那似乎很容易处理。您对数组进行排序，并为每个元素应用——本质上——对每对的二进制搜索进行扭曲。正如人们所说，在 mod-space 上进行二进制搜索留给读者。

我有几个面试题，我以同样的方式使用，找出候选人是否有勇气质疑这个问题。这个问题可能具有两者的元素，必须质疑实数和实数上的模型的想法，然后解决一个易于处理的问题（一个相当传统的搜索数据结构问题）。

当我提出这些问题时，第一部分可能是一个“陷阱”问题，我会让他们对这个问题困惑几分钟，然后将问题重新呈现为一个易于处理的问题，只是为了移动一起采访。