algorithm - 在行和列中查找具有相同编号的位置

Question

给定一个仅包含 0 和 1 的等维二维数组(即 n x n)，我如何找到(忽略矩阵 [i][i])第 i 行全为 0 和第 i 列全部为 1。如果不存在这样的 i 则返回 -1。

ma​​trix[i][i] 可以有任何东西。

预计时间复杂度为O(n)

例如

对于给定的 4 x 4 矩阵

1 1 0 0
0 1 0 0
1 1 0 1
0 1 0 0

答案是 1(i 从零开始)，因为第 2 行全为 0，第 2 列全为 1(忽略 [1, 1] 处的值)。

Answer 1

首先，这样的矩阵只有 1 个或 0 个答案。

1. 从第一行开始走直到没有找到 1(对角线值 应该被忽略)。
2. 开始按列走，直到找不到 0。如果到达对角线，则转到第 1 步。
3. 重复1直到不出矩阵。

例如你在索引为 i 的行或列中出去，你应该验证 i 它是否是一个答案。答案将是 i 或 -1。

由于每个 Action 处理 1 行或 1 列的 Action 总数将是 n+n，为了验证所需的答案，遍历 1 行和列将总共消耗 n+n 个 Action ，我们有 4*n 个 Action ，这是一个 < strong>O(n) 复杂度。

步行示例:

0 0 0 1 S S S S S S
S S S 1 S S S S S S
S S S 0 0 0 1 S S S
S S S S S S 1 S S S
S S S S S S 1 S S S
S S S S S S 1 S S S
S S S S S S 1 0 0 0 X
S S S S S S S S S S
S S S S S S S S S S
S S S S S S S S S S

您应该验证 7 的答案。