Soh*_*amC 1 arrays algorithm data-structures
最近在一次采访中,我被问到一个非常有趣的问题.
假设给出了大量n个对象,其中每个对象代表给定日期公司的股票价格.考虑到两者之间没有缺失日期,并且任何给定日期的股票价格保持不变.我们希望找到任意两个日期之间的平均股票价格,即对于给定货币对(startDate,endDate),以及startDate <endDate.
显然,通过遍历整个阵列来找到平均值,可以得到算法的O(n)解.但是,我们可以优化计算,我们可以将数据存储在某些数据结构中或进行某种预处理吗？面试官要求提供O(1)解决方案.
当然有.您可以预处理数组,以便每个元素现在存储该日期和之前所有日期的股票价格的累积总和 ; 这个预处理将花费n(n)时间为n个日期.
然后,要计算O(1)时间内给定日期范围内的平均股票价格,您:
(如果你使用整数变量进行此操作,累积和可能会溢出并在某个时刻回绕.这实际上(大部分)是无害的,因为步骤2中的减法仍然会给出正确的结果,只要你永远不会要求在如此长的范围内获得平均值,甚至超过该范围的总和也会溢出.
使用浮动,您不必担心溢出,但随着累积总和的增加,您将慢慢失去精度.因此,以后日期的结果可能稍微不那么精确.除非你的股票价格数据可以追溯到几个世纪,否则这在实践中仍然不太可能成为问题.)
顺便说一句,如果您愿意接受O(log n)查询时间,您还可以使用分段树来解决此问题.这是更慢和更复杂的,但有一个优点:它允许您在O(log n)时间内修改任何日期的价格,而不是累积和方法的O(n).此外,它不会受到长距离的精度损失问题的影响.