algorithm - 写一个高效的方法

Question

我被指示写一个在方阵中找到“十字”的方法(这道题中的所有矩阵都由 1 和 0 组成)。

k 是一个cross 如果在第 k 行中所有元素都是零 0 并且在第 k 列中所有元素都是 1(除了 [k][k] 中的元素等于 0 )

例如，2是这个矩阵中的十字:
1 0 1
0 1 1
0 0 0

我需要编写一个有效的方法，如果矩阵中有交叉则返回 k，如果没有则返回 -1。

我在考虑用下面的设计写一个方法:

遍历矩阵对角线中所有数字的循环，检查是否为 0。如果找到 0，我检查该行中所有数字的总和，看它是否等于 0。如果是，我检查列中所有数字的总和是否等于矩阵的长度。

如果是，则返回 k。如果不是，则返回 -1。不过，我不确定我的解决方案的复杂程度。如果这是 O(n^2) 我没有得到所有的分数。如果有人能告诉我我的建议是否足够有效(以及它的有效水平是多少)，我会很高兴。

将不胜感激。 :)

Answer 1

现在可能有点晚了，但编辑引起了我的注意。

这个问题让我想起了名人问题。我们可以观察到最多可能有一个交叉。因此，我们可以开始以下程序:

1. 初始化一个带有交叉候选的堆栈(初始堆栈是从 1 到列数(或 0 到列数 - 1)的序列。在任何考试之前，所有这些数字都可能是交叉)
2. 只要栈中有两个元素就进行迭代
   1. 从堆栈中选择两个最顶层的元素，我们称它们为i 和j
   2. 检查第 i 行和 j 列中的条目。如果条目为 0，则 j 不能是叉号(因为第 j 列只能包含 1)。如果entry是1，i不能是叉号
   3. 将仍然可以成为十字架的一个候选人放回堆栈
3. 现在我们只有一个候选项，需要检查它是否真的是十字架(通过检查它的行和列)。

整体时间复杂度为O(n)。