java - 检查是否存在具有相同值的行和列的有效算法？

Question

我试图用最少的运行时间来解决这个问题。如果给定一个二维数组，如果存在一行所有值都等于 x，并且有一列所有值都等于 x，我们需要返回 x。例如，对于下面的二维数组，

0 3 1

2 3 1

1 1 1

我们应该返回 1，因为最后一行和最后一列都是相同的值 1。如果不存在这样的数字，我们可以返回 -1。

我知道有很多方法可以解决这个问题，其中大部分都是 O(n^2)，我想知道是否有一种有效的方法(即 O(n))来找到这样的值。 (其中 n 表示此数组中的单元格数)

Answer 1

好的，您阐明了您认为 O(n) 是二维数组中值的数量。

我将概述伪代码中的方法，您可以根据自己的喜好将其转换为 Java 或 C++。你的问题被标记为两者，伪代码很简单，可以直接翻译成 C++ 或 Java。或者 Perl。或者 Python...

第 1 部分

让我们从第一个简单的步骤开始，即如何检查是否有任何行包含相同的值。伪代码是基本的:

• 从第0行开始，n=0
• 检查矩阵 [n][0] 到 [n][m-1](其中 m 是矩阵中的列数)是否包含相同的值。如果是这样，您就找到了。
• 否则，增加 n 以转到下一行，直到到达矩阵的底部。

你应该能够理解这一点。这是基本的“计算机科学 101”内容。

第 2 部分

现在，让我们修改此伪代码以同时检查列。修改上述伪代码如下。

• 创建两个一维 vector ，将第一个称为 top_values 或其他名称，其大小为 m，即矩阵中的列数。调用第二个 flags，它是一个 boolean 标志 vector ，它们的大小也是 m。
• 当您扫描第 0 行时，在第一部分给出的伪代码中，将第 0 行的值复制到 top_values 中。即，将 matrix[0][x] 复制到 top_values[x] 中。同时将 flags[x] 设置为 true(您甚至可以在扫描第 0 个之前将所有 flags 初始化为 true行，没关系)。
• 当您扫描剩余的每一行时，使用第 1 部分中给出的伪代码，将 matrix[y][x](其中 y 是您正在扫描的行号)与 最高值[x]。如果它们不相同，则将 flags[x] 设置为 false。
• 在第 1 部分伪代码的末尾，检查您的 flags vector 。如果其中的任何值仍然为真，则矩阵中有一列的值相同。

你的家庭作业是对上面的伪代码稍作调整，以告诉你在某些行或列中哪个值是相同的。