algorithm - 用相邻单元格的平均值替换矩阵中的每个单元格

Question

要求:必须就地完成。

例如:

给定矩阵

1, 2, 3
4, 5, 6
7, 8, 9

应该用它的 3*3 个相邻单元格和它自己的总和的平均值代替:

(1+2+4+5)/4,       (2+1+3+4+5+6)/6 ,            (3+2+6+5)/4
(1+2+5+4+7+8)/6,   (1+2+3+4+5+6+7+8+9)/9,       (2+3+5+6+8+9)/6
(4+5+7+8)/4,       (4+5+6+7+8+9)/6,             (5+6+8+9)/4

即:

All floating number convert to int

3,      3.5(3), 4             3, 3, 4
4.5(4),  5, 5.5(5)  =>        4, 5, 5
6,      6.5(6), 7             6, 6, 7

我试着遍历矩阵并更新每个单元格，但我发现这会影响 future 的计算:

假设我将原来的 1 更新为 3，但是当我尝试更新原来的 2 时，原来的 1 现在变成了 3。

复制原始矩阵来计算平均值是一种解决方法，但这是一个坏主意，我们可以在不使用那么多空间的情况下实现吗？

Answer 1

在大多数情况下，您应该只创建原始矩阵的副本并将其用于计算平均值。除非创建矩阵的副本会使用比可用内存更多的内存，否则开销应该可以忽略不计。

如果您有一个真的 大矩阵，您可以使用“滚动”备份(缺少更好的术语)。假设您逐行更新单元格，并且您当前在第 n 行中。您不需要备份 n-2 行，因为这些单元格不再相关，也不需要备份 n+1 行，因为它们仍然是原始的值。所以你可以只保留前一行和当前行的备份。每当您前进到下一行时，丢弃前一行的备份，将当前行的备份移动到上一行，并创建新的当前行的备份。

一些伪代码(不考虑任何边缘情况):

previous = []  # or whatever works for the first row
for i in len(matrix):
    current = copy(matrix[i])
    for k in len(matrix[i]):
         matrix[i][k] = previous[k-1] + ... + current[k] + ... matrix[i+1][k+1] / 9
    previous = current

(您还可以保留下 行的备份，这样您就可以只对所有值使用备份行，而不必进行区分。)