相关疑难解决方法(0)

我有一个看起来像这样的矩阵:

| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 1 |

我应该找到这个矩阵是否有一个用所有1填充的列.在这个矩阵中它是第4列.据说时间复杂度是O(n),内存是O(1).

该矩阵表示一组(人)的二元关系.n是集合的大小,因此矩阵的大小是n * n.

我可以看到两种可能的解决方案

• 取第一列,浏览它,如果看到零,跳到下一列,依此类推.但这种算法的最坏情况是O(n ²);
• 下一个,如果我将所有列的总和超过我可以在O(n)中给出答案.但是在任务条件下我们没有说过计算过的总和.如果我将计算它们,复杂性也将是O(n ²);

还有其他方法吗？