问题: 给你两个数组,求两个数组的交集。
比如: A = 1 4 7 3 5 , B = 2 9 3 8 5, 那么交集就是 3 5.
每一次从B数组中取一值,然后在A数组里逐个比较,如果有相等的,则保存。该算法复杂度为 O(MN). M, N 分别为数组 A B 的长度。
先将A,B数组排序。因为A B 都排过序,所以,每一次从B数组取值后,可以利用二分查找看是否在数组A里有B所对应的值,这样复杂度变成了O(N lg M)。 这里,如果N 比 M 大,可以从A中取值,然后在B中判断是否有A的值,这样,复杂度为 O(M lg N)。
利用hashtable.。先把A中的值存在hashtable里,然后对于每一个B中的值,判断是否在A中存在,因为hashtable查找的平均复杂度为 O(1), 所以,整个算法复杂度为O(N), 但是,这里的空间复杂度为 O(M) 。但是,这种方法适合数组比较小的情况。因为如果A数组比较大,hashtable会出现collision的情况,这样,查找的平均复杂度就不再是 O(1)。
先将A,B排序。因为数组A B均排过序,所以,我们可以用两个“指针”分别指向两个数组的头部,如果其中一个比另一个小,移动小的那个数组的指针;如果相等,那么那个值是在交集里,保存该值,这时,同时移动两个数组的指针。一直这样操作下去,直到有一个指针已经超过数组范围。
public LinkedListintersection(int[] A, int[] B) { if (A == null || B == null || A.length == 0 || B.length == 0) return null; LinkedList list = new LinkedList (); int pointerA = 0; int pointerB = 0; while (pointerA < A.length && pointerB < B.length) { if (A[pointerA] < B[pointerB]) pointerA++; else if (A[pointerA] > B[pointerB]) pointerB++; else { list.add(A[pointerA]); pointerA++; pointerB++; } } return list; }
通过上面的算法可以得知,该算法复杂度为O(N + M).
扩展:
给两个排序的数组,求两个数组的并集。
思路:也是用两个指针,不相等的时候,输出小的那个数,然后移动指针,相同的时候,输出任意一个,然后同时移动指针。
用两个数组分别记录A,B数组中数字出现的个数。这两个数组的下标代表数组中的数,值代表这个数出现的次数。然后将两个数组对位相加,如果某个位置上的值>=2,说明是A,B数组中都出现的元素。