MyException - 我的异常网
当前位置:我的异常网» J2SE » 怎么求两个数组的交集

怎么求两个数组的交集

www.MyException.Cn  网友分享于:2013-12-11  浏览:359次
如何求两个数组的交集?
有两个数组a{1,5,8,10,14,15,17,18,20,22,24,25,28}和b{2,4,6,8,10,12},如何求出他们之间的交集?要求效率越高越好
注:数组都是从小到大排序好的

------解决方案--------------------
其实解决b中的重复也很简单,只要在遍历b的时候,判断一下当前的这个元素是否和前面的元素一样,如果一样,那就continue执行下一次循环。

所以总结起来看,在这个算法中,如果a是第一个放到set中去的话,那么a有没有排序无所谓;但是为了避免麻烦,b最好是排序的。

好了,代码就不写了。已经分析好了。坐等楼下提供别的算法...
------解决方案--------------------
既然是排序好的,
那么可以直接对比a和b的元素
i,j是a,b中元素的当前位置
Java code
while(i<a.length && j < b.length)
{
if(a[i] < b[j])
{
    i++;
}
else if (a[i] == b[j])
{
    输出这个元素;
    i++;
    j++;
}
else
{
    j++;
}
}

------解决方案--------------------
探讨
既然是排序好的,
那么可以直接对比a和b的元素
i,j是a,b中元素的当前位置
Java codewhile(i<a.length&& j< b.length)
{if(a[i]< b[j])
{
i++;
}elseif (a[i]== b[j])
{
输出这个元素;
i++;
j++;
}else
{
j++;
}
}

------解决方案--------------------
偷懒的写法:
Java code

int[] a = {1,5,8,10,14,15,17,18,20,22,24,25,28};
int[] b = {2,4,6,8,10,12};

List   list   =   new   ArrayList(Arrays.asList(a));   
list.retainAll(Arrays.asList(b));   //   list   中的就是交集了.

------解决方案--------------------
代码如下,如果你想降低时间复杂度,可以在getDuplicated方法里多加判断,因为是排过序的,当第二个数组的元素大小超过了第一个数组的最后一个值的时候,就没有必要继续了;还有当前元素如果小于第一个数组的第一个元素是,也没必要继续,直接跳到下一次循环。等等...
Java code
import java.util.*;

public class STest {
    private static int count, index;
    
    public static void getDuplicated(int[] a, int[] b){
        Set<Integer> set = new LinkedHashSet<Integer>();
        
        for(int i=0; i<a.length; i++)
            set.add(a[i]);
        
        for(int j=0; j<b.length; j++){
            int setSize = set.size();
            
            if(j>0){
                if(b[j] == b[j-1])
                    continue;
            }
            
            set.add(b[j]);
            
            if(set.size() == setSize){
                b[index] = b[j];
                count ++;
                index ++;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] first = {1,5,8,8,10,100,14,15,70,70,17,18,18,20,22,24,25,28};
        int[] second = {2,4,4,4,4,6,8,8,8,8,10,12};
        
        getDuplicated(first, second);
        
        for(int i=0; i<count; i++)
            System.out.print(second[i] +" ");
    }
}

------解决方案--------------------
高效率的上面都说了,我写个低效率的,优点在于没用API中现成的方法,笔试时经常碰到这种变态要求。。。
Java code

public class TestUnion {
    public static void main(String args[]){
        int a[] = {1,5,8,10,14,15,17,18,20,22,24,25,28};
        int b[] = {2,4,6,8,10,12};
        for(int i = 0; i < b.length; i++){
            for(int j = 0; j < a.length; j++){
                if(b[i] == a[j]){
                    System.out.print(" " + b[i]);
                    break;
                }
                else
                    continue;
            }
        }
    }
}

------解决方案--------------------
知道散列集HashSet 吗,它在数据组织上类似于数学上的数组,可以进行“交”、“并”、“差”等运算。
例如:
 Integer one=new Integer(1),
two=new Integer(2),
three=new Integer(3),
four=new Integer(4),
five=new Integer(5),
six=new Integer(6);
 HashSet A=new HashSet(),
B=new HashSet(),
tempSet=new HashSet();
 A.add(one); 
 A.add(two);
 A.add(three);

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有