algorithm - 双链表找到最接近平均值的元素

Question

有一个排序的双链表（C++ STL std::list），例如“1,1,2,3,4,5,6”，以及如何找到最接近列表平均值的元素通过扫描一次？（最接近平均 22/7 的元素是 3）

Answer 1

这里的关键是它是一个双链表。

您需要做的是同时从双方出发，边走边计算平均值。

如果到目前为止的平均值大于右迭代器的元素，则增加左迭代器。

如果平均值小于左迭代器的元素，则减少右迭代器。

如果平均值介于两者之间，则将其中一个或两个向内移动（假设我们向左移动）。

当迭代器相遇时，停止。查看当前元素，以及一个后移一个前移的元素，看看哪个最接近。

为什么这样有效：

如果平均值小于左边的值，它可以保持较小，所以那个元素（或左边的一个位置）可能是最接近的，因此我们不能移动那个迭代器。

如果平均值大于左值，由于所有尚未处理的元素都大于左值，平均值不可能低于左值，因此我们可以安全地增加左迭代器。从技术上讲，左边的值仍然可以是最接近的，但不是左边一个位置的值（这就是我们需要查看周围元素的原因）。下面以增加 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 是最接近的。