求两个数组的交集跟并集

求两个数组的交集和并集

晚上闲来无事，想起前两天查资料时候，看到别人一篇博客标题关于数组的交集和并集，晚上也随便写写，权当督促自己坚持经常练习练习写写小Demo。如下，先来一段求有序数组的交集的代码，代码如下：

public static List<Integer> getIntersectionSorted(int[] a,int[] b){
		if(a == null || b == null)
			throw new NullPointerException("Array is Empty");
		List<Integer> mixList = new ArrayList<Integer>();
        int i = 0;
        int j = 0;
        while(i < a.length && j < b.length){
        	 if(a[i] == b[j]){
        		 mixList.add(a[i]);
        		 //当前结点值相同，所以下次判断结点，先往前移动一次再说
        		 do{   
        			 i++;
        		 }while(i < a.length -1 && a[i] == a[i+1]);//当前判断结点下一个结点值是否等于前一个，如果等于避免无谓的再一圈循环，直接移动到下一个结点
        		 
        		 do{
        			 j++;
        		 } while(j < b.length -1 && b[j] == b[j+1]);
        		 continue;
        	 }else if(a[i] > b[j]){
        		 j++;
        		 continue;
        	 }else if(a[i] < b[j]){
        		 i++;
        		 continue;
        	 }
        }
		return mixList;
	}

由以上代码我们知道上面的求法最差时间负责度为O(m+n)。如果我们的数组没有排序，以上的方式肯定行不通，下面贴出求两无序数组的并集的代码，代码如下：

 public static List<Integer> getIntersectionNotSortedUsingWhile(int[] a,int[] b){
		if(a == null || b == null)
			throw new NullPointerException("Array is Empty");
		List<Integer> mixList = new ArrayList<Integer>();
		int startIndex = 0;
		int i = 0;
		while(i<b.length){
			int temp = b[i];
			int j = startIndex;
			while(j <a.length){
				while(j < a.length -1 && a[j] == a[j+1]){
					j++;
				}
				if(a[j] == temp){//当前判断结点下一个结点值是否等于前一个，如果等于避免无意义的移动
					mixList.add(temp);
					swap(a,startIndex,j); //此处操作：将数组元素分成两部分，一部分已经判断过的元素，每次元素判断过后，将该元素移动到判断过的部分，下次判断从未判断部分开始继续判断
										  //因为已经添加到mixList的元素没有必要再下一次循环去判断的必要了。（类似插入排序的意思）
					startIndex++;
					break;
				}
				j++;
			}
			i++;
		}
		return mixList;
	} 	
   
	public static List<Integer> getIntersectionNotSortedUsingFor(int[] a,int[] b){
		if(a == null || b == null)
			throw new NullPointerException("Array is Empty");
		List<Integer> mixList = new ArrayList<Integer>();
		int startIndex = 0;
		for(int i = 0;i<b.length;i++){
			int temp = b[i];
			for(int j = startIndex;j<a.length;j++){
				while(j < a.length -1 && a[j] == a[j+1]){//当前判断结点下一个结点值是否等于前一个，如果等于避免无意义的移动
					j++;
				}
				if(a[j] == temp){
					mixList.add(temp);
					swap(a,startIndex,j);//同上
					startIndex++;
					break;
				}
			}
		}
		return mixList;
	} 
	
	public static void swap(int[] a,int m,int n){
		int temp = a[m];
		a[m] = a[n];
		a[n] = temp;
	}

以上代码可知，以上算法的效率可能没有达到最优，自己感觉效率还没有那么差吧，稍微借鉴了下插入排序做了小小的优化，时间复杂度也相对稳定。

下面把自己求两个数组的并集的练习也贴出来，有什么地方不对，还希望园友指出。先求有序两个数组的并集代码如下：

public static List<Integer> getUnionSetSorted(int[] a,int[] b){
		if(a == null || b == null)
			throw new NullPointerException("Array is Empty");
		List<Integer> mixList = new ArrayList<Integer>();
		int i = 0,j = 0;
		while(i < a.length && j < b.length){
			 if(a[i] == b[j]){
				 mixList.add(a[i]);
				 i++;
				 while(i< a.length -1 && a[i] == a[i+1]){ //判断当前元素和下一个元素是否重复，重复元素直接前进一位
					 i++;
				 }
				 j++;
				 while(j< b.length -1 && b[j] == b[j+1]){
					 j++;
				 }

			 }else if(a[i] < b[j]){
				 mixList.add(a[i]);
				 i++;
				 while(i< a.length -1 && a[i] == a[i+1]){
					 i++;
				 }
			 }else if(a[i] > b[j]){
				 mixList.add(b[j]);
				 j++;
				 while(j< b.length -1 && b[j] == b[j+1]){
					 j++;
				 }
		
			 }
		}
		while(i <a.length){ //判断合并循环退出时，a数组还没有添加完
			mixList.add(a[i]);
			i++;
			 while(i< a.length -1 && a[i] == a[i+1]){
				 i++;
			 }
		}
		while(j < b.length){//同上
			mixList.add(b[j]);
			j++;
			while(i< a.length -1 && a[i] == a[i+1]){
				 i++;
			 }
		}
		return mixList;
	}

该代码的最差时间负责度也为O(M + N)。

下面我们求两个无序数组的并集的实现，代码如下：

public static List<Integer> getUnionSetNotSorted(int[] a,int[] b){
		if(a == null || b == null)
			throw new NullPointerException("Array is Empty");
		List<Integer> mixList = new ArrayList<Integer>();
		for(int i = 0;i<a.length;i++){
			 if(!mixList.contains(a[i])){
				 mixList.add(a[i]);
			 }
		}
		for(int i = 0;i<b.length;i++){
			if(!mixList.contains(b[i])){
				mixList.add(b[i]);
			}
		}
		return mixList;
	}

该代码的实现时间负责度为O(n2)。最后求两个无序的数组的并集代码的效率还有待提高，暂时没有想到效率更高的实现，路过的园友还望不吝指教。

求两个数组的交集跟并集

相关推荐