矩阵和算法面试问题

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)时间复杂度。如果正确，是否存在更快的算法？

- Brahadeesh

---

问题 - 如果其中一行是[1,2,3]，并且其中一列是[2,3,1]，那是否被认为是匹配的？ - corsiKa

不，它们必须按照相同的顺序。 - Brahadeesh

它不是n的三次方吗？如果您将每个n行与每个n列进行比较，那么将进行n*n次比较，并且每次比较可能最长为n（最坏情况）。使用随机数据平均值可能为n平方。 - phkahler

它的T(n)=4T(n/2)+O(1)，这是O(n^log4)=O(n^2)。 - Brahadeesh

抱歉，这个问题已经添加了一段时间，但我必须问一下，这不是n^2吗？你可能会进行n/2次比较，所以你的递归不能是+ O(1)。这里的洞察力/技巧是什么，本质上防止你将每一行与每一列进行比较？ - Kakira

Answer 1

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

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

当然，当n大且有许多几乎相同的行和列时，trie最有趣。但即使在矩阵中所有整数都不同的最坏情况下，该结构也允许清晰的算法...

- Adrien Plisson

---

他说矩阵是随机填充的。Trie树利用了常见前缀的优势。此外，您仍然需要O(n*n)扫描所有数据来创建Trie树。 - phkahler

@phkahler：你说得对。然而，你可能不需要一开始就建立trie。你可以在比较列和行的同时建立trie。这样trie就成为了一种记忆化结构，不需要O(n*n)来扫描所有行。 - Adrien Plisson

想想看，我想出来的每个算法都有一个几乎是O(n*n)的最坏时间。如果整数确实是随机的，那么Trie将允许过滤掉大多数情况，但如果除了最后一行和最后一列之外所有元素都相等，则会出现最坏情况... - Adrien Plisson

@Adrien Plisson，我的怎么样了？ - orlp

@nightcracker：我必须承认，我很难理解你的算法...我不明白为什么构建对角线不是O(nn)，与构建trie一样...(trie解决方案在最坏情况下似乎是O(nn+nn)，一次通过从行构建trie(nn)，另一次测试列) - Adrien Plisson

@Adrien Plisson：你说得对。我想我需要重新考虑一下。抱歉。 - orlp

Answer 2

你可以通过计算每行/列的总和并仅在与列的总和匹配的行上缩小暴力比较范围（最终你必须这样做）来加快平均情况。

这不会增加最坏情况（所有行/列具有相同的总和），但如果你的输入是真正随机的，那么“这不会发生” :-)

- corsiKa

---

是的，我考虑过这个。但是我没有将其纳入其中，因为它不会减少运行时间的上限。是否有一种算法可以在O(n logn)或O(n)的时间内完成这项任务？ - Brahadeesh

似乎因为每一行都必须与每一列进行比较，所以你无法避免（行列-->nn）的运行时间。话虽如此，他们也曾经这样说过排序，直到出现了lg-n排序... - corsiKa

是的，这就是我在寻找的东西。某种基于快速排序的二维适应方法可以解决这个问题。 - Brahadeesh

@Jasie：在堆排序和其他一些算法中，O(nlogn)是最坏情况下的时间复杂度上限。 - phkahler

Answer 3

这可能只适用于非奇异矩阵（不确定），但是...

设A为一个方阵（可能是非奇异的）NxN矩阵。设A'为A的转置。如果我们创建矩阵B，使其为A和A'的水平连接（换句话说[A A']），并将其放入RREF形式，则左半部分将得到对角线上的所有一，并且右半部分将得到某个方阵。

例如：

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。

例子

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在右半部分最左侧的列中意味着它是第一行。

- Phonon

---

什么是rref，它的复杂度是多少？ - Brahadeesh

Answer 4

不看您的算法或以前答案中的任何方法，但由于矩阵一开始就有n^2个元素，我认为没有比这更好的方法 :)

- dcn

---

这个参数不正确。有些方阵问题有n^2个元素，但可以在线性时间内解决。我想说的是，你可以拥有比输入大小更好的算法。 - Srikanth

当然，有些问题可能不需要考虑整个输入（例如，“确定n个元素序列中的第一个数字”），而我没有为给定问题的O（n ^ 2）下限陈述“参数”。我想说的是，对于这个特定的问题，显然你可能需要考虑矩阵中的所有元素！ - dcn

Answer 5

如果矩阵是真正的随机的...

你可以创建一个指向按第一个元素排序的列的指针列表。然后创建一个类似的按它们的第一个元素排序的行列表。这需要O(n*logn)。

接下来创建一个初始化为0的每个排序列表的索引。如果第一个元素匹配，你必须比较整行。如果它们不匹配，则增加具有最低起始元素的那个的索引（要么移动到下一行，要么移动到下一列）。由于每个索引只循环从0到n-1一次，所以你最多只有2*n次比较，除非所有的行和列都以相同的数字开头，但我们说的是一个随机数矩阵。

在最坏的情况下，行/列比较的时间是n，但在平均情况下，使用随机数据预计为O(1)。

因此，两种O(nlogn)的排序和扫描2*n*1给出了预期的运行时间为O(nlogn)。当然，这是假设数据是随机的。对于大部分元素都是相同值的大矩阵，最坏情况仍将是n**3。

- phkahler