比較算法

Question

我有2個數組（A和B），其中包含有些差異的相似數據。我想返回僅在A中的對象數組和僅在B中的另一個對象數組。到目前爲止，我一直在想：

1. 一些優化蠻力（這是微不足道的）
2. 排序的陣列和使用二進制搜索。

我的其他選擇是什麼？任何語言/解決方案都是公平遊戲。

Answer 1

您可以對兩個數組進行排序，然後同時對兩個數組進行線性掃描。這將是用於排序的O（nlogn）算法和用於掃描/建立新陣列的O（n）。

Answer 2

嘗試使用集合。他們通常有一個差異（）方法（或類似的東西），返回到你想要的。就那麼簡單。一旦語言不可知，如何創建集合或將差異轉換爲數組就是使用一般方法完成的。

Set A = createSetA(); 
Set B = createSetB(); 

Array onlyAElements = transformToArray(A.difference(B)); 
Array onlyBElements = transformToArray(B.difference(A)); 

或者，您可以對兩個數組進行排序，並同時獲取兩個差異數組。類似於

int aIndex = 0; 
int bIndex = 0; 

Array aOnly = new Array(); 
Array bOnly = new Array(); 

while (aIndex != a.length || bIndex != b.length) 
{ 
    if (A[aIndex] == B[bIndex] 
    { 
     aIndex++; 
     bIndex++; 
    } 
    else if (A[aIndex] > B[bIndex]) 
    { 
     aOnly.add(A[aIndex]); 
     aIndex++; 
    } 
    else 
    { 
     bOnly.add(B[bIndex]); 
     bIndex++; 
    } 
} 

您應該記住在越界時出現一些錯誤。但代碼只是爲了得到主要想法。

Answer 3

我沒有實現或算法超越什麼的已經說過，但我想我會留在C＃/ LINQ該解決方案的人誰可能會發現這個問題，並要做到這一點：

var a = new int[] { 1, 2, 3, 6, 7, 8, 9, 10 }; 
    var b = new int[] { 1, 2, 3, 4, 5, 6, 7 }; 

    int[] addedToA = a.Except(b); 
    int[] missingFromA = b.Except(a); 

    foreach (var i in addedToA) 
    { 
     Console.Write("{0} ", i); 
    } 
    Console.WriteLine(); 
    foreach (var i in missingFromA) 
    { 
     Console.Write("{0} ", i); 
    } 

這將打印：

8 9 10 
4 5 

Answer 4

很多這將取決於你有什麼類型的數據。你提到排序，所以我認爲它的元素是可比的。隨着套尺寸m和n，這將需要進行排序，這將佔主導地位。 （漸近地說，如果你進行二分搜索或者走這兩個列表都沒有關係，走這兩個列表應該是O(m + n)。）當然，如果你正在使用更好的排序算法可用的數據，比如帶有基數排序的整數，你應該可以降到O(m + n)。

使用集合（正如其他人所暗示的）隱含地建議使用散列，這肯定會使您的問題更容易。如果散列A中的所有元素（O(m)），並將散列集中的所有散列存儲在內存中，則散列B（O(n)）並檢測散列集中可能發生衝突的位置。這成爲優化的問題：您必須評估經典的速度 - 內存摺衷。散列集越大，碰撞檢查的速度就越快。這將在O(m + n)中運行。

值得注意的是，你可以證明任何你要求的算法至少會在至少m + n時間內運行，因爲需要查看所有的輸入。

Answer 5

我想將數組A的元素填充到散列表中，然後遍歷數組B在哈希表中進行查找以有效地確定B中的哪些元素也在A.然後在遍歷數組A的同時在散列表中對B的元素執行同樣的操作。這將始終是O（N）。