算法：如何在矩陣中找到填充全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。

我可以看到2個可能的解決方案：

• 在第一個欄，通過它，如果看到零，跳到下一列等。但是這種算法的最壞情況將是O（n ）;
• 下一個，如果我將有所有列的總和，我可以在O（n）中給出答案。但是在任務條件中並沒有說我們已經計算了總和。如果我計算它們，複雜度也將是O（n ）;

其他解決方案？

Answer 1

讓我對你想要做的事情進行一個非常瘋狂的猜測。從提提示：

1. 數組代表了人民的關係
2. 您發現全1列
3. 你正在努力尋找一個O(n)算法

好了，你可以在O(n)中不這樣做，我只能證明它是O(n^2)。

但我野生猜測是，你做一個經典的celebrity identification problem，那你誤解問題。

名人是人都知道的人，但不知道任何[其他人] 。

我的名人身份問題，你正在努力尋找這樣的：對你正在努力尋找

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

Answer 2

假設任意內容，您無法避免O的最壞情況（n ）。 ^*您必須訪問每個列中您想考慮的每個元素，而在最壞的情況下，您必須考慮所有列。

---

_{*另外假設n是這裏的矩陣維數，而不是元素的總數。}

Answer 3

如果不假設任意內容（如奧利的答案），你可以每行編碼爲二進制標誌的無符號整數，那麼你可以做到在O（n）和O（ 1）只需重複執行每行的邏輯AND以獲得最新結果。

最後一組標誌將只有相關列也是一個。

Answer 4

矩陣的輸入是什麼？

如果您得到每列的數字，即在您的示例中（十進制）14,8,4,31,1，您可以創建一個數字a，並將n的二進制數字設置爲1（在本例中爲31 ）。如果這個數字等於其中一個列號，則其中一列全部爲1。

Answer 5

我的解決方案是我們首先假設所有列都有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+" "); 
     } 
    } 
}