如何在 O(1) 时间内实现以下算法？

Question

我有一个用整数填充的二维数组。我想要一种在 O(1) 时间内找到数组某些部分的平均值的方法。例如，我有数组 A[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; 并且算法的输入是边界。所以Algorithm(int top, int bottom, int left, int right)。如果 top = 1 , bottom = 2, left = 1, right = 2 ，则该部分将从第二行到第三行以及从第二列到第三列。所以平均值是 (5+6+8+9)/4.

Answer 1

我将给出一个提示，说明该怎么做。你可以建立一个辅助数据结构来方便计算。但是，该数据结构需要超过 O(1) 的时间来计算，因此只有在多次计算时才有用。

提示是累积值很有用。我将在一个维度上举一个例子。您需要弄清楚如何扩展它。假设您有以下数据：

1      2      3      4      5
10    -3      6      6     -2

和你有同样的问题。如何在恒定时间内解决这个问题？那么，创建另一个具有累加和的数据结构：

1      2      3      4      5
10     7     13     19     17

现在，如果你想要 2-5 的 sum，你可以只计算 17 - 10（即 2 之前的一个索引）。您可以将其除以 (1 + 5 - 2) 得到平均值。

Answer 2

可以写前缀table的总和。

这个例子看起来像你的数组

1 2 3

4 5 6

7 8 9

前缀数组：

1 3 6

5 12 21

12 27 45

然后当你想计算你的例子时：

X = (prefix[bottom][right] - prefix[bottom][left-1] - prefix[top-1][right] + prefix[top-1][left-1]) / (right - left + 1) * (bottom - top + 1);

X = (45 - 12 - 6 + 1) / 4 = 7;

用于填充前缀数组的模型：

  For(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
           prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] + array[i][j] - prefix[i-1][j-1];
        }
    }

*代码用C++语言编写 **n - 行数，m - 列数

如何在 O(1) 时间内实现以下算法？

How do I implement the following algorithm in O(1) time?

algorithm

multidimensional-array

data-structures

runtime