如何在 O(1) 时间内实现以下算法?
How do I implement the following algorithm in O(1) time?
我有一个用整数填充的二维数组。我想要一种在 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.
我将给出一个提示,说明该怎么做。你可以建立一个辅助数据结构来方便计算。但是,该数据结构需要超过 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) 得到平均值。
可以写前缀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) 时间内找到数组某些部分的平均值的方法。例如,我有数组 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.
我将给出一个提示,说明该怎么做。你可以建立一个辅助数据结构来方便计算。但是,该数据结构需要超过 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) 得到平均值。
可以写前缀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 - 列数