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）a。n如果此数字等于列号之一，则其中一列全为 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 回答