矩阵，算法面试问题
这是我的面试问题之一。
我们有一个包含整数的矩阵(没有提供范围)。矩阵是用整数随机填充的。我们需要设计一种算法来找到那些与列完全匹配的行。我们需要返回匹配的行号和列号。匹配元素的顺序是相同的。例如，如果第i行与第j列匹配，并且第i行包含元素- 1,4,5,6,3。则第j列也将包含元素- 1,4,5,6,3。大小为n x n。我的解决方案是：
RCEQUAL(A,i1..12,j1..j2)// A is n*n matrix
if(i2-i1==2 && j2-j1==2 && b[n*i1+1..n*i2] has [j1..j2])
use brute force to check if the rows and columns are same.
if (any rows and columns are same)
store the row and column numbers in b[1..n^2].//b[1],b[n+2],b[2n+3].. store row no,
// b[2..n+1] stores columns that
//match with row 1, b[n+3..2n+2]
//those that match with row 2,etc..
else
RCEQUAL(A,1..n/2,1..n/2);
RCEQUAL(A,n/2..n,1..n/2);
RCEQUAL(A,1..n/2,n/2..n);
RCEQUAL(A,n/2..n,n/2..n);取O(n^2)。这是正确的吗？如果正确，有没有更快的算法？
回答 5
Stack Overflow用户
发布于 2011-03-24 01:08:14
您可以从行中的数据构建一个trie。然后，您可以将列与trie进行比较。
这将允许在列的开头与任何行都不匹配时立即退出。此外，这还允许您在一次遍历中针对所有行检查一列。
当然，当n很大(为一个小的n设置一个trie是不值得的)，并且有许多行和列完全相同时，trie是最有趣的。但即使在最坏的情况下，矩阵中的所有整数都是不同的，其结构也允许一个清晰的算法...
Stack Overflow用户
发布于 2011-03-24 00:57:23
您可以通过计算每行/列的总和并将暴力比较(最终必须这样做)缩小到与列的总和匹配的行上，从而加快平均情况的速度。
这不会增加最坏的情况(都有相同的和)，但如果你的输入真的是随机的，那么“不会发生”:-)
Stack Overflow用户
发布于 2011-03-24 01:17:53
这可能只适用于非奇异矩阵(不确定)，但是...
设A是正方形(可能是非奇异的) NxN矩阵。设A‘是A的转置，如果我们创建矩阵B，使得它是A和A’(换句话说，A，A')的水平连接，并将其放入RREF形式，我们将得到左半部分中的所有1和右半部分中的某个方阵的对角线。
示例：
A = 1 2
3 4
A'= 1 3
2 4
B = 1 2 1 3
3 4 2 4
rref(B) = 1 0 0 -2
0 1 0.5 2.5另一方面，如果A的一列等于A的一行，那么A的列将等于A‘的列。然后，我们将获得rref(B)的右半部分的列中的另一个1 in。
示例
A=
1 2 3 4 5
2 6 -3 4 6
3 8 -7 6 9
4 1 7 -5 3
5 2 4 -1 -1
A'=
1 2 3 4 5
2 6 8 1 2
3 -3 -7 7 4
4 4 6 -5 -1
5 6 9 3 -1
B =
1 2 3 4 5 1 2 3 4 5
2 6 -3 4 6 2 6 8 1 2
3 8 -7 6 9 3 -3 -7 7 4
4 1 7 -5 3 4 4 6 -5 -1
5 2 4 -1 -1 5 6 9 3 -1
rref(B)=
1 0 0 0 0 1.000 -3.689 -5.921 3.080 0.495
0 1 0 0 0 0 6.054 9.394 -3.097 -1.024
0 0 1 0 0 0 2.378 3.842 -0.961 0.009
0 0 0 1 0 0 -0.565 -0.842 1.823 0.802
0 0 0 0 1 0 -2.258 -3.605 0.540 0.662在右半部分的顶行中的1.000表示A的第一列与其行中的一行匹配。1.000在右半部分的最左边这一事实意味着它是第一行。
https://stackoverflow.com/questions/5408799
复制相似问题
腾讯云开发者
