矩阵,算法面试问题

Question

这是我的一个面试问题.

我们有一个包含整数的矩阵(没有提供范围).矩阵随机填充整数.我们需要设计一种算法,该算法可以找到与列完全匹配的行.我们需要返回匹配的行号和列号.匹配元素的顺序是相同的.例如,如果,我的行与第j列匹配,并且我的行包含元素 - [1,4,5,6,3].然后第j列也将包含元素 - [1,4,5,6,3].大小是nx 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

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

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

当然，当trien很大时（为小trie 设置trien不值得）以及当有许多行和列完全相同时，trie 最有趣。但即使在矩阵中所有整数都不同的最坏情况下，该结构也允许使用清晰的算法......