<分区>
我有三个整数数组 A、B、C。
我想找到最接近的 a,b,c 使得
a < b < c 其中a属于A，b属于B，c属于C。
当我说最接近时，我的意思是 (b-a) + (c-b) = (c-a) 是最小值。
自己提出这个问题。我只能想到蛮力 O(N^3)
标签 algorithm
<分区>
我有三个整数数组 A、B、C。
我想找到最接近的 a,b,c 使得
a < b < c 其中a属于A，b属于B，c属于C。
当我说最接近时，我的意思是 (b-a) + (c-b) = (c-a) 是最小值。
自己提出这个问题。我只能想到蛮力 O(N^3)
最佳答案
正如 TravisJ 提到的，您要优化的值是 (b-a) + (c-b) = c - a因此，您只需要最小化两个元素之间的差异 - 一个来自第一组，一个来自第三组。我能想到的一种可能的方法是 - 对 C 中的元素进行排序然后遍历 A 中的所有元素.对于每个 a来自 A您可以在已排序的 C 中进行二分查找找到元素 c最接近给定的 a .优化所有值 c-a通过这种方式获得。此解决方案将具有复杂性 O(n * log(n)) .
编辑:(再次按照 TravisJ 的建议):您需要确保有一个 b来自 B这样 a < b < c .为此，您还需要对 B 进行排序.现在对于每个 a您在 B 中执行二进制搜索找到最小的 b大于 a然后是 c 中的另一个二进制文件找到最小的 c大于 b .
关于algorithm - 从遵循趋势的数组中查找最接近的元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27569827/