algorithm - 在二维数组中找到菱形的最快方法是什么？

Question

这是我的问题的可视化：

我需要找到存储在正方形中的最有价值的菱形。我想了几天，但直到现在，除了使用'for循环'并检查每一个可能的菱形之外，我没有找到任何其他东西。你们怎么看？这是我能做到的唯一方法吗？:P 谢谢 :)

Answer 1

这是我的想法：

第一次迭代，你遍历矩阵，但对角线。你从最左上角的地方开始，在那里你可以适应你的菱形（或菱形的边），然后你看一下菱形大小所覆盖的元素。

• 你首先检查元素 (0,1) 和 (1,0) (a)
• 接下来检查 (0,2) 和 (1,1) (b)
• (1,1), (2,0) (b)
• (0,3), (1,2) (c)
• (1,2), (2,1) (c)
• ...

我希望你能拿到考试令。你对这些元素所做的就是对它们进行总结：e(0,1) + e(1,0) = 11，e(0,2) + e(1,1) = 3等等。您必须注意，当您处理同一行上的元素（上面标有相同字母的元素）时，您不必重新计算总和：一个元素出去，一个进来，因此您只访问两个元素即可获得新的总和。

第二次迭代，你对角线遍历矩阵，但从不同的一侧。您从右上角开始，处理之前计算的总和。因此，您将检查的第一对将位于(0,3), (1,4)。您做的事情与之前完全相同：再次计算总和。

现在，在第二次迭代结束时，每个处理的字段实际上都包含在该字段中具有上角的稀疏菱形的总和。3x3 rhomb 的示例如下图所示：

第 3 步从图像中可以看出，大小为n的稀疏菱形“缺少”另一个稀疏菱形——大小为(n-1)的稀疏菱形。迭代 1 和 2 正是为图像中所有大小为n的稀疏菱形求和的过程。因此，作为第三步，我们再次运行第一次和第二次迭代，但不是使用我们正在搜索的大小 ( n )，而是使用大小(n-1)。请注意，大小为 1 的“搜索”等于输入矩阵（例如，如果 n=2，则对于第 3 步，您无需计算任何内容）。

最后，对顶部位置 (0,2) 的 3x3 菱形感兴趣的总和是前两次迭代的 (0,2) 和第三步的 (1,2) 总和. 您可以将这两者相加：对于前两次传递的结果矩阵中的每个元素在位置 (x,y) 处，您从第三步结果矩阵中添加位置 (x,y+1) 处的元素。现在你只需要找到最大值，你就有了菱形的最大值和位置的答案。

您在 4 遍中完成所有这些（您可以在计算第二遍时跟踪最大值） - 所以这将给出正方形大小大小的复杂O(4*n^2) = O(n^2)性n。

希望很清楚，如果我的回答搞砸了，请要求澄清。

---

2x2 菱形的示例

第一次通过

 -1 11  3  7  5     * / * * * 
 -1  9 14 12  3     / * * * *
 -1 12 18  4  6     * * * * * 
 -1 11  3  6  2    * * * * * 
 -1 -1 -1 -1 -1     * * * * *

第二遍

 -1 25 15 10 -1    * * * \ *
 -1 27 18 18 -1    * * * * \
 -1 15 24  6 -1    * * * * *
 -1 -1 -1 -1 -1    * * * * *
 -1 -1 -1 -1 -1    * * * * *

第三步

由于n=1，第三遍不需要计算任何东西，第三遍的输出是输入矩阵

 1  2  2  2  2
 9  1  5  3  1
 8  9  9  2  3
 3  9  2  3  1
 2  1  3  1  1

现在，我们只需要将第二次迭代的输出与第三步的输出相加（上移一位）。我们得到：

 -1 26 20 13 -1    
 -1 36 27 20 -1    
 -1 24 26  9 -1    
 -1 -1 -1 -1 -1    
 -1 -1 -1 -1 -1    

回答 在 (1,1) 处有上角的菱形是最有价值的菱形，总和为 31。

注意： -1是菱形边不适合的地方——未定义的总和。您可以在程序中以任何您想要的方式标记它（特别是如果您的矩阵中实际上可以有负值）。在第二遍中，您可以将具有未定义元素的任何总和设置为未定义。

注意2：无论菱形大小如何，当您在矩阵中滑动菱形边时，总有一个数字进来，而另一个数字从总和中出来（除非您输入新行）。

注3：第2遍和第2遍中菱形的第一个位置在数组中用/或标记\

---

示例 3x3 菱形

让我在同一个矩阵上做一个 3x3 菱形，以表明在一般情况下复杂度是O(n^2)（n正方形大小的大小在哪里），而不仅仅是 2x2 菱形。

让我们称输入矩阵z[][]，第一次传递f[][]后和第二次传递后的矩阵，s[][]

第一次通过

1. f[0][2] = z[0][2] + z[1][1] + z[2][0] == 11 （一种）
2. f[0][3] = z[0][3] + z[1][2] + z[2][1] == 16 (二)
3. f[1][2] = f[0][3] - z[0][3] + z[3][0] == 17 (二)
4. f[0][4] = z[0][4] + z[1][3] + z[2][2] == 14 （C）
5. f[1][3] = f[0][4] - z[0][4] + z[3][1] == 21 （C）
6. f[2][2] = f[1][3] - z[1][3] + z[4][0] == 20 （C）
7. f[1][4] = z[1][4] + z[2][3] + z[3][2] == 5 (d)
8. f[2][3] = f[1][4] - z[1][4] + z[4][1] == 5 (d)
9. f[2][4] = z[2][4] + z[3][3] + z[4][2] == 9 (e)

您最多访问每个元素一次。用不同字母标记的是同一行上的总和。m在该行的第一个 sum 中，您必须对rhomb 一侧的元素求和，我们称它为m x mrhomb。在该行的所有其他总和中，您始终必须准确访问 3 个元素：前一个总和、输出的元素（带有-符号的元素）和输入的元素（+符号）。

 -1 -1 11 16 14 
 -1 -1 17 21  5 
 -1 -1 20  5  9 
 -1 -1 -1 -1 -1 
 -1 -1 -1 -1 -1 

第二遍

然后你在第二遍中做类似的事情（我不打算把它们写出来），你只是少了一点元素。

 -1 -1 41 -1 -1 
 -1 -1 -1 -1 -1 
 -1 -1 -1 -1 -1 
 -1 -1 -1 -1 -1 
 -1 -1 -1 -1 -1 

第三步

此步骤与2x2 示例的第 1 次和第 2 次迭代完全相同。因此，2x2 稀疏菱形的总和是：

 -1 25 15 10 -1    
 -1 27 18 18 -1    
 -1 15 24  6 -1    
 -1 -1 -1 -1 -1    
 -1 -1 -1 -1 -1    

当我们将它与第二次迭代的输出相加时，我们得到：

 -1 -1 59 -1 -1 
 -1 -1 -1 -1 -1 
 -1 -1 -1 -1 -1 
 -1 -1 -1 -1 -1 
 -1 -1 -1 -1 -1 

答案只有一个 3x3 菱形适合矩阵，所以矩阵中只剩下一个元素，这正是唯一适合的菱形的总和：59。

Answer 2

如果问题是关于在菱形“内核”中找到最大和，那么是的，有更快的算法。

penelope 提出的算法是一个很好的起点——然而，当菱形尺寸变大时，所需的输入和输出部分和的数量会增加。这可以通过二维第一遍来避免，它在 2 个方向上对角积分值。

[ a b c d]  --> integrate a, a+f, a+f+k, a+f+k+p right down    
[ e f g h]      then integrate the elements in positions c,f,i etc. 
[ i j k l]
[ m n o p] 

与查找对齐平方和相比，这种方法的缺点是必须计算一组单独的对角线，因为 (x+y) 是奇数，而 (x+y) 是偶数；那么结果来自采样 8 个积分和而不是 4 个。

我相信通过从左到右和从上到下集成最容易理解该方法（求和区域）

[1 2 0 3]       [1 3 3 6]        here every cell contains the summed area
[0 0 1 1]       [1 3 4 8]        of M[I][J] := sigma i=0..I,j=0..J m[i][j]
[1 0 3 1]  -->  [2 4 8 13]
[0 1 1 1]       [2 5 10 16] 

要获得区域（8..16,100..983），只需访问角元素：

Sigma i=8..16,j=100..983 m[i][j] :== M[7][99]+M[16][983]-M[7][983]-M[16][99]

当要积分的形状旋转45度时，我们要计算两组积分。如果这是一个棋盘，则分别用于白色和黑色方块。然后每个菱形将由来自一个矩阵 M_odd 的 N*N 大小的求和区域和来自另一个求和区域矩阵 M_even 的 (N-1)*(N-1) 大小的求和区域组成（反之亦然）。这可以扩展到具有相同复杂性的任何菱形大小。（并且当 N=1 或 N=2 时，可以优化从矩阵 m 中添加元素，并使用矩阵 M 来表示 N>2 的平方）。

评论：也许这与佩内洛普的建议相同，但是，我无法弄清楚，因为缺乏从 5 元素菱形到任意大小的概括。