算法：如何找到在矩阵中的列装的所有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).

此矩阵再presents一组（人）的二元关系。 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 ² ）;

• Take the first column, go through it, if see zero, jump on the next column and so on. But the worst case of this algorithm will be O(n²);
• The next one, if I will have a sum of all columns than I can give an answer in O(n). But it's not said at task conditions that we have computed sums. And if I will compute them, the complexity will be also O(n²);

任何其他的解决办法？

推荐答案

让我花很胡乱猜测你正在努力做的事情。自提的提示：

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

1. 重新对人民present关系数组
2. 您正在寻找一列全1
3. 您正在努力寻找一个 O（N）算法

1. The array represent relation on people
2. You are finding a column with all 1s
3. You are trying to find an O(n) algorithm

那么，你可以这样做，在 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）解决方案。

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