問題： 給你兩個數(shù)組，求兩個數(shù)組的交集。
比如： A = [1, 4, 7, 3, 5] ， B = [2, 9, 3, 8, 5]， 那么交集就是 [3, 5] .
方法一：
每一次從B數(shù)組中取一值，然后在A數(shù)組里逐個比較，如果有相等的，則保存。該算法復(fù)雜度為 O(MN). M, N 分別為數(shù)組 A B 的長度。
方法二：
先將A,B數(shù)組排序。因?yàn)锳 B 都排過序，所以，每一次從B數(shù)組取值后，可以利用二分查找看是否在數(shù)組A里有B所對應(yīng)的值，這樣復(fù)雜度變成了O(N lg M)。 這里，如果N 比 M 大，可以從A中取值，然后在B中判斷是否有A的值，這樣，復(fù)雜度為 O(M lg N)。
方法三：
利用hashtable.。先把A中的值存在hashtable里，然后對于每一個B中的值，判斷是否在A中存在，因?yàn)閔ashtable查找的平均復(fù)雜度為 O(1), 所以，整個算法復(fù)雜度為O(N), 但是，這里的空間復(fù)雜度為 O(M) 。但是，這種方法適合數(shù)組比較小的情況。因?yàn)槿绻鸄數(shù)組比較大，hashtable會出現(xiàn)collision（沖突）的情況，這樣，查找的平均復(fù)雜度就不再是 O(1)。
方法四：游標(biāo)（★★★）：
先將A, B排序。因?yàn)閿?shù)組A, B均排過序，所以，我們可以用兩個“指針”分別指向兩個數(shù)組的頭部，如果其中一個比另一個小，移動小的那個數(shù)組的指針；如果相等，那么那個值是在交集里，保存該值，這時，同時移動兩個數(shù)組的指針。一直這樣操作下去，直到有一個指針已經(jīng)超過數(shù)組范圍。
public LinkedList<Integer> intersection(int[] A, int[] B) {
if (A == null || B == null || A.length == 0 || B.length == 0) return null;
LinkedList<Integer> result = new LinkedList<Integer>();
int pA = 0;
int pB = 0;
while (pA < A.length && pB < B.length) {
if (A[pA] < B[pB]) pA ++;
else if (A[pA] > B[pB]) pB++;
else {
result.add(A[pA]);
pA++;
pB++;
}
}
return result;
}
通過上面的算法可以得知，該算法復(fù)雜度為O(N + M).
** 擴(kuò)展 **：
給兩個排序的數(shù)組，求兩個數(shù)組的并集。
思路：也是用兩個指針，不相等的時候，輸出小的那個數(shù)，然后移動指針，相同的時候，輸出任意一個，然后同時移動指針。
方法五：使用數(shù)組（位圖的思想）
用兩個數(shù)組分別記錄A，B數(shù)組中數(shù)字出現(xiàn)的個數(shù)。這兩個數(shù)組的下標(biāo)代表數(shù)組中的數(shù)，值代表這個數(shù)出現(xiàn)的次數(shù)。然后比較每一個相同位置中數(shù)組的值，如果都不為0，說明下標(biāo)所代表的數(shù)字在A，B中都存在，相加，統(tǒng)計出這個數(shù)組出現(xiàn)的總次數(shù)。如果有一個為0，說明不是公共元素。
