6

我有一个问题，一个好的解决方案。我希望那里有更好的解决方案。

问题

我有一个包含大约 200,000 个整数的数组。给定两个索引 i1 和 i2，我需要计算 i1 和 i2 之间所有元素的总和。数组中的每个整数都在 1 到 4 之间（包括 1 和 4）。例如：

a = [1, 3, 2, 4, 3, 2, 4, 1];
subsection_sum(a, 0, 3); // returns 6: (1 + 3 + 2)

此操作将执行大约 200,000 次，因此需要非常快。for 循环中的一个简单计数器是 O(n)，而且太慢了。数组构建后从不修改，所以有一个相对昂贵的预处理阶段是可以的。

到目前为止我最好的解决方案

该算法在 O(log n) 时间内工作：

首先用零填充原始数组，直到它的长度是 2 的幂。接下来，将数组分成两个相等的部分并存储每个部分的总和。然后将数组分成四部分并存储每个部分的总和。然后是八分之一。继续这样做，直到数组被分成 2 个元素长的部分。对于上面的 8 元素数组，这需要两个步骤：

halves = [(a[0] + a[1] + a[2] + a[3]), (a[4] + a[5] + a[6] + a[7])]
quarters = [(a[0] + a[1]), (a[2] + a[3]), (a[4] + a[5]), (a[6] + a[7])]

然后给定两个索引，现在可以在 O(log n) 时间内计算出 subsection_sum。例如，subsection_sum(a, 2, 7) == quarters[1] + halves[1]。

4

2 回答 2

14

引入一个包含累积和的辅助数组。也就是说，辅助数组的元素具有原始数组i的元素0到的总和。i子数组和就是辅助数组中两个元素的差。这将在恒定时间内给出结果，O(1)。

这取决于subsection_sum问题中给出的函数的不变量：

subsection_sum(a, 0, i2) = subsection_sum(a, 0, i1) + subsection_sum(a, i1, i2)

我假设的地方i1 <= i2。重新排列，我们有：

subsection_sum(a, i1, i2) = subsection_sum(a, 0, i2) - subsection_sum(a, 0, i1)

请注意，右侧的总和均从 开始0。辅助数组可以被视为缓存从零开始的和的值subsection_sum(a, 0, i)，对于所有的i。

于 2011-05-22T14:26:02.957 回答
3

如果您能负担得起O(n)额外的存储空间，您可以创建一个查找表，其第一个元素是输入数组中索引到（包括）i处的元素的总和。在伪代码中：0i

def computeLookupTable(arr):
    let n = arr.length
    let lookupTable = new Array()

    lookupTable[0] = arr[0]

    for i=1 to n:
        lookupTable[i] = arr[i] + lookupTable[i-1]

    return lookupTable

然后，您可以使用此表来计算array两者之间所有元素的总和，i1并i2通过取差

lookupTable[i2] - lookupTable[i1]

这需要恒定的时间。

于 2011-05-22T14:33:52.357 回答