6

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

| 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

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

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

还有其他解决方案吗?

4

5 回答 5

7

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


* 还假设n这里是矩阵维度,而不是元素总数。

于 2013-05-27T10:26:22.687 回答
6

让我对你正在尝试做的事情进行一个非常疯狂的猜测。提及以下内容的提示:

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

于 2013-05-27T11:59:27.837 回答
1

如果您假设任意内容(如 Oli 的回答)并且您可以将每一行编码为带有二进制标志的无符号整数,那么您可以通过重复执行逻辑AND来在 O(n) 和 O(1) 中执行每一行都有最新的结果。

最后一组标志将只有相关列也是一个的标志。

于 2013-05-27T10:33:36.847 回答
0

矩阵的输入是什么?

如果您为每列获得一个数字,即在您的示例中(十进制)14、8、4、31、1,您可以创建一个二进制数字设置为 1 的数字(在本例中为 31)an如果此数字等于列号之一,则其中一列全为 1。

于 2013-05-27T10:39:20.397 回答
0

我的解决方案是,我们首先假设所有列都有 1,然后我们逐行遍历我们仍然拥有的可能解决方案,并切割不能成为解决方案的列。

此解决方案是用 Java 编写的:

解决方案 1:O(n^2) 直截了当

public class Main
{
    // Given A: an M x N matrix
    public static ArrayList<Integer> solve (Integer [][] matrix)
    {
        // Assuming all columns have 1s, we have list S
        ArrayList<Integer> S = new ArrayList<Integer>();

        // S = { 1, 2, .., N }
        for (int i=0; i < matrix[0].length; i++)
        {
            S.add(i);
        }

        // For Row i: 1..M
        for (Integer i = 0; i < matrix.length; i++)
        {
            // For Column j in list S
            for (Integer j : S)
            {
                if (matrix[i][j] != 1)
                {
                    S.remove(j);
                }
            }
        }

        return S;
    }

    public static void main (String [] args)
    {
        int [][] matrix =
        {
            {1,1,1},
            {0,1,1},
            {0,0,1},
        };

        ArrayList<Integer> columns = solve (matrix);

        System.out.print(" columns that have 1s are: ");

        for (Integer n : columns) System.out.print(n+" ");
    }
}

解决方案 2:使用自定义数据结构的 O(n)

private class Column
{
    public ArrayList<Integer> data;
    public int count;

    public Column ()
    {
        data = new ArrayList<Integer>();
        count = 0;
    }

    public void add (int val)
    {
        data.add(val);
        count += val;
    }
}

public class Main
{

    public static void main (String [] args)
    {
        Column [] matrix =
        {
            new Column (),
            new Column (),
            new Column ()
        };

        matrix[0].add(1);
        matrix[0].add(0);
        matrix[0].add(0);

        matrix[1].add(1);
        matrix[1].add(1);
        matrix[1].add(0);

        matrix[2].add(1);
        matrix[2].add(1);
        matrix[2].add(1);

        System.out.print(" columns that have 1s are: ");

        for (Column column : matrix)
        {
             if (column.count == column.data.size())
                 System.out.print(n+" ");
        }
    }
}
于 2013-05-27T11:05:40.440 回答