三路設置不相交

這是我即將進行的測試中練習題的一個問題。我希望得到幫助，找到解決這個問題的更有效的解決方案。現在，我知道我可以通過使用3個簡單的for循環來解決這類問題，但那將是O(N^3)。三路設置不相交

此外，我相信以某種方式合併二進制搜索將是最好的方式，並給我O(log n)在我正在尋找的答案。不幸的是，我有點卡住了。

三通設置不相交問題定義如下：給定三套物品，甲，乙，和Ç，它們是三路不相交的，如果沒有共同的元素所有三組，即不存在x，使得x在A，B，和C。

假設A，B，和Ç是項集可訂購（整數）;此外，假設可以對O（n log n）時間進行整數分類。給出一個O（n log n）算法來決定這些集合是否是三路集合不相交的。

感謝您的任何援助

來源

2013-03-04 Plazsma

這些集合是否需要成對分離？ – user1952500 2013-03-04 05:55:01

問題陳述給出瞭如何解決問題的明顯暗示。假設3組是數學集合（每個集合中的元素是唯一的），只需將3個集合混合在一起並對它們進行排序，然後線性遍歷列表並搜索是否存在同一個項目的3個實例。時間複雜度主要是排序，這是O(n log n)。輔助空間的複雜度至多爲O(n)。

另一種解決方案是使用基於散列的映射/字典。只需計算3套物品的頻率。如果任何項目的頻率等於3（這可以在檢索更新頻率時檢查），則3組不是3路分離。插入，訪問和修改可以在O(1)分期複雜度下完成，所以時間複雜度爲O(n)。空間複雜度也是O(n)。

來源

2013-03-04 05:56:51 nhahtdh

謝謝。所以你可以直線運行直到'len-2'並且做一些事情，比如if（arr [i] == arr [i + 1] && arr [i] == arr [i + 2]）return false; ？ – Plazsma 2013-03-04 06:29:09

@Plazsma：這是實現它的一種方式。 – nhahtdh 2013-03-04 07:57:50

如果複雜性約束（既不空間或常數項），這可以在O（N）來解決。創建兩個位圖，將整數從A映射到第一個，將整數從B映射到第二個。然後遍歷第三個（C）直到耗盡，或者找到一個條目，其中設置了bitmapA（testInt）和bitmapB（testInt）。

來源

2013-03-04 02:22:31 bjmckenz

如果使用位集，空間複雜度取決於2個集合A和B中的最大數量，如果最大數量很大，則空間複雜度很差。 – nhahtdh 2013-03-04 05:37:00

我們可以用o（n）來解決這個問題。如果我們使用Set數據結構並考慮初始容量和，這是可能的。

public static boolean checkThreeWaySetDisjointness(Set<Integer> a, Set<Integer> b, Set<Integer> c) 
    { 
     int capacity = Math.round((a.size() + b.size())/0.75f) + 1; 
     Set<Integer> container = new HashSet<Integer>(capacity); 
     container.addAll(a); 
     for (int element : b) 
     { 
      if (!container.add(element)) 
      { 
       if (c.contains(element)) 
       { 
        return false; 
       } 
      } 
     } 
     return true; 
    }

我們正在創造新的一組容器，因爲如果我們開始在任何現有的一組A/B/C直接添加，一旦達到其實際尺寸的75％的容量，內部java會創造新的Hashset及複印件整個現有的Set中。這種開銷將具有O（n）的複雜性。因此，我們在這裏創建新的HashSet的大小爲容量，這將確保不會有複製的開銷。然後複製整個Set a，然後繼續添加來自Set b的一個一個元素。在Java中，如果add（）返回false意味着元素已經存在於當前集合中。如果是的話，只需在第三個設置c中檢查相同。 HashSet的方法add和contains包含O（1）的複雜性，所以這整個代碼運行在O（n）中。

來源

2017-12-24 07:17:50 Tejas

三路設置不相交

回答

相關問題