算法:如何在矩阵中找到一列填充所有1,时间复杂度为O(n)？

Question

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

| 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 ²);

还有其他方法吗？

Answer 1

假设任意内容,你无法避免最坏情况下的O(n ²).^* 您必须访问要考虑的每列中的每个元素,在最坏的情况下,您必须考虑所有列.

_{*还假设这n是矩阵维度,而不是元素总数.}

Answer 2

让我对你想要做的事情进行非常疯狂的猜测.提及的提示:

1. 数组代表人的关系
2. 您正在查找包含全1的列
3. 您正在尝试查找O(n)算法

好吧,你不能这样做,O(n)我可以证明它O(n^2)只是.

但我的野生猜测是,你做一个经典的名人身份的问题,那你误解的问题.

名人是每个人都知道的人,但不知道任何[其他人].

我是名人识别问题,你试图找到类似的东西:

Find the number i where
a[i][x] = 1 for all x            -> every one knows the celebrity
a[x][i] = 0 for all x != i       -> the celebrity doesn't know anyone else

事实上,通过对你想要找到的东西的这种额外限制,有一个O(n)解决方案.