鑑於2個陣列，返回未包含在兩個數組

我有一次採訪中，並沒有下文所述的問題，一個元素：鑑於2個陣列，返回未包含在兩個數組

給定兩個數組，請計算結果：得到工會，然後取出從工會交叉。例如

int a[] = {1, 3, 4, 5, 7}; 
int b[] = {5, 3, 8, 10}; // didn't mention if has the same value. 

result = {1,4,7,8,10}

這是我的想法：

排序a，b。
使用a中的'dichotomy search'檢查每個項目b。如果沒有找到，通過。否則，無論從a刪除此項目，b
結果=留在a +元素的元素留在b

我知道這是一個糟糕的算法，但仍然是聊勝於無。有沒有比這更好的方法？

來源

2014-10-09 carysun

「二分法搜索」 - 你的意思是二進制搜索？ – 2014-10-09 03:51:06

尋找'std :: set_difference'實現，它的C++，但你可以得到想法 – P0W 2014-10-09 04:01:23

假設數組a有n個元素，b有m個元素...（nlogn）+搜索每個元素爲O（nlogn）+生成結果數組爲O（n + m），總共爲O（nlogn）複雜度（或O（mlogm）+ O（nlogn）取決於是否n 2014-10-09 04:05:44

有很多方法來解決這個問題。一種方法是：

1. construct hash-map using distinct array elements of array a with elements as keys and 1 is a value. 
2. for every element,e in array b 
    if e in hash-map 
     set value of that key to 0 
    else 
    add e to result array. 
3.add all keys from hash-map whose values 1 to result array.

來源

2014-10-09 04:17:36 Karunakar

另一種做法則是：

通過加入列表加入兩份名單
排序加入列表
步行路程，徹底消除任何元素多次出現

這有一個缺點：它不起作用，如果輸入列表已經有雙合。但既然我們在談論集合和集合論，我也會期望輸入集在數學意義上是集合的。

來源

2014-10-09 15:46:26

另一個（在我看來是最好的）做法：

你不需要通過你的這兩個列表的搜索。你可以依次遍歷它們：

排序a和b
宣佈一個空結果集
採取迭代器兩個列表和重複以下步驟：
- 如果迭代值不相等：
  如果迭代器值相等，則將較小的數字添加到結果集並遞增所屬的迭代器
- ：
  遞增兩個迭代器而不向結果集添加內容
- 如果一個迭代器到達終點：
  另一組的所有剩餘的元素添加到結果

來源

2014-10-09 15:56:30

鑑於2個陣列，返回未包含在兩個數組

回答

相關問題