有一个排序的双链表(C++ STL std :: list),例如"1,1,2,3,4,5,6",以及如何找到最接近列表平均值的元素通过扫描一次？(最接近平均22/7的元素是3)
这里的关键是它是一个双链表.
你需要做的是同时从两边走,计算你的平均值.
如果到目前为止的平均值大于正确的迭代器元素,则增加左迭代器.
如果平均值小于左迭代器的元素,则减小右迭代器.
如果平均值在两者之间,则向内移动一个或两个(假设我们向左移动).
当迭代器相遇时,停止.查看当前元素,以及返回的元素和向前看的元素,以查看哪个元素最接近.
为什么这样有效:
如果平均值小于左值,它可以保持较小,因此元素(或左边的一个位置)可能是最接近的,因此我们不能移动该迭代器.
如果平均值大于左值,由于尚未处理的所有元素都大于左值,因此平均值不可能低于左值,因此我们可以安全地增加左迭代器.从技术上讲,左值仍然可以是最接近的值,但不是左边一个位置的值(这就是我们需要查看周围元素的原因).以下面3到4的增加为例.
同样适用于正确的价值.
例:
1,1,2,3,4,5,6 Average
L R 7/2 = 3.5
L R 8/3 = 2.667
L R 10/4 = 2.5
L R 13/5 = 2.6
L R 18/6 = 3
L R 22/7 = 3.14
LR
然后看3,4和5,我们看到3是最接近的.