假设有一个股票价格的实时提要,你如何计算它的一个子集的平均值(比如过去一周)?
这是一个面试问题。我可以想出一个用O(n^2)实现的算法,但面试官想要的算法是O(n)。
发布于 2017-10-20 21:56:01
一种有用的方法是计算数组的累积和。
这意味着累积和数组中的每个条目都是所有先前价格的总和。
这很有用,因为您可以使用单个减法对输入的任何特定子数组生成和。
请注意,当新的输入到达时,您只需要1次加法即可计算新的累积和(因为您只需将新元素添加到旧的累积和中)。
发布于 2017-10-20 22:15:50
另一种方法类似于基因组学中的计算偏差。
如果要计算过去一周的平均值,请创建一个包含移动窗口总和的变量。创建条目时,将该条目添加到上述sum变量中,并从中减去移动窗口中最旧的条目。因为窗口的大小是恒定的,所以过去一周的平均值就是过去一周条目数量的移动和。
https://stackoverflow.com/questions/46850592
复制相似问题