查找两个矩阵之间的偏移量
我有两个二进制(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向右移动一行。我的目标是找到两个矩阵之间的偏移量(例如r+1)。
我的解决方案-在矩阵A中添加一个全为0的列，并检查它是否等于矩阵B。继续添加c-1列。对行重复相同的过程。当两个矩阵相等时停止。
这似乎是一种非常低效的方式。有没有更好的方法来做这件事？
回答 1
Stack Overflow用户
发布于 2019-06-07 13:18:35
目前，您的算法的时间复杂度为O(rc^2)。我可以提出一个使用散列的时间复杂度为O(rc)的解决方案。我将讨论如何解决矩阵右移某些列的情况下的问题。同样的想法也适用于其他三种类型的轮班。需要注意的一件事是，根据我的理解，在你的例子中，第二个矩阵移位了1列，而不是1行，因为所有的值都移位了1列。我将在下面的解决方案中使用此约定。
让我们假设，我们有两个1xc矩阵。现在，我们可以把它们想象成具有c位的二进制字符串。我们将使用O(c)内存和O(c)时间对两个字符串进行散列，并存储第二个字符串的所有后缀和第一个字符串的所有前缀的散列值。现在，我们可以迭代所有可能的移位并进行检查。例如，要检查矩阵是否移位了3列，我们可以只检查第二个字符串的前三个值是否为零，以及第二个字符串的(c-3)长度后缀是否与O(1)中第一个字符串的(c-3)长度前缀具有相同的散列值。我们需要存储第二个字符串的最长零前缀的长度，以便在开始迭代之前有效地执行此操作。
现在，当我们有一个rxc矩阵时，我们可以对两个矩阵的每一列进行散列，然后将rxc矩阵转换为1xc字符串，其中字符串的第i位数字将等于矩阵第i列的散列值，并以相同的方式应用上述算法。
https://stackoverflow.com/questions/56487891
复制相似问题
腾讯云开发者
