C庫查找兩個數組之間的區別

給定2個數組我需要一個C函數/庫，它將查找2個數組之間的不同。C庫查找兩個數組之間的區別

array1[] ={"a","b","c","e"} 
array2[] ={"a","c","e"}

和函數應該返回

{"b"}

這2個陣列保證進行排序，但不相同的尺寸。我只需要這個功能就快。

2011-11-27 Icestorm

「b」是唯一的，因爲它不會在這兩個數組中都不存在，我還沒有嘗試過任何東西，只需要多次遍歷兩個數組，但我需要它比這更快。 – Icestorm

@Iststorm：好的，道歉，也許在某種程度上，你可以稱之爲'b''unique'，儘管如果你有數組{'，a，b，b}和'{c，c ，d，d}'。最好避免這種不必要的含糊術語。我認爲你正在尋找「設置差異」或「對稱差異」。 –

它爲什麼要快？爲什麼它應該使用庫函數？ – wildplasser

下面是一個O（n）的算法：

創建兩個指針，每個初始化在每個陣列的第一元素指向。每次* p1 < * p2，將* p1添加到輸出數組並增加p1。 p2相同。如果它們相等，則增加兩者。

我會讓你弄清楚如何處理重複的元素，以及當一個指針到達它的數組末尾時該怎麼做。

[此外，如果你能使用C++，那麼你應該只使用std::set_symmetric_difference]

2011-11-27 23:27:52

這是缺少'* p1 == * p2'時發生的情況的描述，非？ –

@Kerrek：給讀者留下的練習... –

讓他讓他自己解決鍛鍊... – Beginner

@Oli查爾斯沃思

如果ARR1 [] = { 「A」，「B」，」在這種情況下，我猜你的邏輯將遍歷數組中的元素（以較低者爲準），但是沒有必要，如下所示：在這種情況下，我猜你的邏輯將會遍歷數組中的元素（以較低者爲準），但並不需要第一個比較只有你能找到結果因此結果是可能的o（1）這種情況.....

2011-11-28 09:14:22

回答