java - 查找两个矩阵之间的偏移量

Question

我有 2 个二进制 (r x c) 矩阵 - 相同大小的矩阵 A 和矩阵 B。矩阵B是矩阵A中的1向左/右/上/下移动一个偏移值得到的。

int a[][] ={
            { 0,0,1,0,0 },
            { 0,1,0,1,0 }, 
            { 1,0,0,0,1 }
        }, 
        b[][] = 
        {
            { 0,0,0,1,0 },
            { 0,0,1,0,1 }, 
            { 0,1,0,0,0 }
        }

在这种情况下，矩阵 B 向右移动一行。我的目标是找到 2 个矩阵之间的偏移量(例如，r+1)。

我的解决方案 - 向矩阵 A 添加一个全为 0 的列，并检查它是否等于矩阵 B。继续添加 c-1 列。对行重复相同的过程。当两个矩阵相等时停止。

这似乎是一种非常低效的方法。有更好的方法吗？

Answer 1

目前您的算法的时间复杂度为 O(rc^2)。我可以提出一个使用哈希的时间复杂度为 O(rc) 的解决方案。 我将讨论如何解决矩阵向右移动某些列时的问题。同样的想法也适用于其他三种类次。需要注意的一件事是，按照我的理解，在您的示例中，第二个矩阵移动了 1 列，而不是 1 行，因为所有值都移动了 1 列。我将在以下解决方案中使用此约定。

假设，我们有两个 1xc 矩阵。现在，我们可以将它们视为具有 c 位的二进制字符串。我们将使用 O(c) 内存和 O(c) 时间对两个字符串进行哈希处理，并存储第二个字符串的所有后缀和第一个字符串的所有前缀的哈希值。现在，我们可以迭代所有可能的类次并检查。例如，要检查矩阵是否移动了 3 列，我们可以只检查第二个字符串的前三个值是否为零以及第二个字符串的 (c-3) 长度后缀是否具有与第二个字符串相同的哈希值(c-3) O(1) 中第一个字符串的长度前缀。我们需要存储第二个字符串的最长零前缀的长度，以便在开始迭代之前有效地进行这项工作。

现在，当我们有一个 rxc 矩阵时，我们可以对两个矩阵的每一列进行哈希处理，然后将 rxc 矩阵转换为 1xc 字符串，其中字符串的第 i 个数字等于第 i 个的哈希值-矩阵的第 列，并以相同的方式应用上述算法。