algorithm - 二维数组相似度

Question

我有两个二维数组，每个数组的大小为 N*N。如果这些子数组的至少 K% 元素在两个数组中具有相同的值和相同的位置，则称这些数组的两个二维子数组是相似的。我需要告诉此类子数组的最大大小以及具有此最大大小的此类子数组的数量。

请帮忙解决这个问题

例子:

假设我有两个二维数组并且 k=50:

---

1 3 5

6 7 8

5 7 9

---

1 5 7

6 7 3

3 7 9

---

在这里，我们可以看到我们在所有子矩阵中有 2 个 2*2 的子矩阵，它们是:

1. 一个

   1 3

   6 7

   乙

   1 5

   6 7

2. 一个

   7 8

   7 9

   乙

   7 3

   7 9

这两个子矩阵都有三个共同元素，而且显然有超过50%的元素是相同的，而且两个子矩阵的位置也相同

但 3*3 矩阵本身有超过 50% 的元素相同。所以答案是最大尺寸为 3，子矩阵数为 1

Answer 1

使用这两个矩阵(A，B)，形成具有元素的第三个矩阵(C):

C(i,j) = { 1 if A(i,j) == B(i,j), else zero}

现在的问题是找到 C 中至少有 k% 1 的最大子矩阵。因此，如果子矩阵的大小为 mxm，则:

Sum of all elements in this submatrix >= (k/100) *m*m.

这可以在 O(N^3) 时间内完成，如下所示:

对于每个元素，计算它之前所有元素的累计和。

D(i,j) = summation ( C(l,h) for l = 0 to i and h = 0 to j )

现在子矩阵的可能大小可以从 (nxn) 到 (1x1)。因此，对于从 n 到 1 的每个大小 (s) 矩阵，遍历子矩阵。

这可以通过 1 个指针 p 来完成，它扫描每个元素并形成子矩阵的左上角。子矩阵的右上角q与p在同一行，但在p+s处有一列。

您可以在 O(1) 时间内检查由 p 和 q 分别作为左上角和右上角组成的子矩阵中的元素之和，因为您知道元素的累积和。

Sum of elements in sub-matrix(p->q) for row r 
  = D( r + q - p, q ) - D( r-1, q ) - D( r + q - p, p - 1 ) + D ( r - 1, p - 1 )

当您找到一个有效矩阵或多个相同大小的有效矩阵时停止。