A、B两个整数集合的交集

  rt，这是一个经典问题。

参考1：http://www.sysexpand.com/?path=exercises/array-intersection

参考2：http://leetcode.com/2010/03/here-is-phone-screening-question-from.html

用数组来模拟（本质上说集合中是没有重复元素的，这里用数组来模拟可以用重复元素），A、B数组长度分别为m和n。总的来说，分为以下几种方案。

方案1：两重循环判断（复杂度 O（m*n））

暴力方法，并且不容易去除重复元素

方案2:Hash Table方法（复杂度 O（m+n））

   将A写入Hash Table，让后B在Hash Tabe中写入过程中判断重复即可。如果没有重复元素，唯一缺点是内存占用量大，可以使用《编程珠玑》中的BitMap方法节省内存。另外Hash过程中可能会有比较多的冲突。

另外，本方法不具有普遍性。

方案3：排序后对A中每个元素在B中进行二分查找（复杂度 O(nlogn+mlogm)）

    这里m<=n。否则排序后对B中每个元素在A中进行二分查找（复杂度 O（n*lgm））

注意，排序的复杂度是O(nlogn+mlogm)，查找的复杂度是O（n*lgm）。

方案4：排序后应用归并排序的思想进行判断（复杂度 O(nlogn+mlogm)）

   指针i和j分别指向A和B的开头，如果对应元素相等即为交集，否则谁小谁的指针加1往后移动。

  注意，排序的复杂度是O(nlogn+mlogm)，归并过程是O（m+n），比方案3更优。

  下面是实现部分，并且去除了重复元素。

/**  * 创建时间：2014年8月16日 上午11:46:12  * 项目名称：Test  * @author Cao Yanfeng   Peking University * @since JDK 1.6.0_21  * 类说明：测试两个数组的交集，交集中不包含重复数  */
public class Intersectionof2ArraysTest {/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stubint[] array1={4,6,2,4,3,5,1};int[] array2={4,4,9,6,8,7,5,5,6,7};LinkedList linkedList=Intersectionof2Arrays(array1, array2);for (Integer integer : linkedList) {System.out.println(integer);}}public static LinkedList Intersectionof2Arrays(int[] array1,int[] array2) {LinkedList linkedList=new LinkedList();int m=array1.length;int n=array2.length;quicSort(array1, 0,m-1);quicSort(array2, 0,n-1);/*初步判断两种没有任何交集的情况*/if (array1[0]>array2[n-1]|array1[m-1]= temp) {end--;}arr[start] = arr[end];while (start < end && arr[start] <= temp) {// 括号中end--之后可能不满足条件start++;}arr[end] = arr[start];}arr[start] = temp;return start;}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！