algorithm - 矩阵、算法面试题

Question

这是我的面试问题之一。

我们有一个包含整数的矩阵(未提供范围)。矩阵随机填充整数。我们需要设计一种算法来找到与列完全匹配的那些行。我们需要返回匹配项的行号和列号。匹配元素的顺序是一样的。例如，如果，第 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)。它是否正确？如果正确，是否有更快的算法？

Answer 1

你可以构建一个 trie从行中的数据。然后您可以将列与 trie 进行比较。

这将允许在列的开头与任何行不匹配时立即退出。这也可以让您一次检查所有行的列。

当然，当 n 很大(为较小的 n 设置一个 trie 是不值得的)并且有很多行和列时，trie 是最有趣的这是完全一样的。但即使在矩阵中所有整数都不同的最坏情况下，该结构也允许使用清晰的算法...