算法:如何在矩阵中找到一列全为 1，时间复杂度为 O(n)? [英] Algorithm: how to find a column in matrix filled with all 1, time complexity O(n)?

问题描述

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

I have a matrix which looks like this:

| 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).

I should find if this matrix has a column filled with all 1. At this matrix it's column 4. And it's said that time complexity is O(n) and memory is O(1).

这个矩阵表示一组(人)的二元关系.n是集合的大小，所以矩阵的大小是n * n.

This matrix represents a binary relation on a set (of people). n is the size of the set, so the size of the matrix is n * n.

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

I can see 2 possible solutions:

• 取第一列，通过它，如果看到零，跳到下一列，依此类推.但是这个算法最坏的情况是 O(n²);
• 下一个，如果我有所有列的总和，那么我可以在 O(n) 中给出答案.但是在任务条件下并没有说我们已经计算了总和.如果我计算它们，复杂度也是 O(n²);

还有其他解决方案吗?

推荐答案

让我大胆猜测一下您要做什么.提到的提示:

Let me take a very wild guess on what you are trying to do. Hint from the mention of:

1. 数组代表人与人之间的关系
2. 您正在查找一个全为 1 的列
3. 您正在尝试寻找O(n) 算法

好吧，你不能在 O(n) 中做到这一点，我可以证明它只是 O(n^2).

Well, you can not do that in O(n) and I can prove that it is O(n^2) only.

但我疯狂的猜测是你在做一个经典的名人识别问题，并且您误解了问题.

But my wild guess is that you doing a classic celebrity identification problem, and that you misunderstood the problem.

名人是其他人都知道但不认识的人认识任何[其他人].

A celebrity is person that is known by every other person, but doesn't know any [other people].

我的名人身份识别问题，您正在尝试查找以下内容:

I celebrity identification problem, you are trying to find something like:

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) 解决方案.

And indeed with this extra constrain on what you are trying to find, there is an O(n) solution.

这篇关于算法:如何在矩阵中找到一列全为 1，时间复杂度为 O(n)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！