2个集合比较——最高效解法(Java实现)

优点:时间复杂度为O(n)级别;

缺点:只适用于Int,以及Int的数字不能过大,集合元素数量不能过多。

理论分析:

两个集合的元素之和以及之积相同则,这两个集合相等。(前提是两个集合的数量一致)

证明: 先证明集合只有两个元素的情况A={a,b} B={x,y}

a+b=x+y,a*b=x*y 联立之后可以得出2组解a=x,b=y;a=y,b=x;说明2个集合相等。

更多的元素的集合。我们只需要假设k元素的时候相等。则k+1个元素是一样证明的,用不完全归纳法即可以解。

下面上代码:

public class SetEqual {

    static boolean  isEqual(Set<Integer> set1,Set<Integer>set2){
        
        if(set1.size()!= set2.size()) return false;
        int sum1=0,sum2=0;
        int multi1=1,multi2=1;
        Iterator<Integer> it1 = set1.iterator();
        while(it1.hasNext()){
            Integer tmp = (Integer) it1.next();
            sum1 += tmp;
            multi1 = multi1*tmp;
        }
        Iterator<Integer> it2 = set2.iterator();
        while(it2.hasNext()){
            Integer tmp = (Integer) it2.next();
            sum2 += tmp;
            multi2 = multi2*tmp;
        }
        
        return  (sum1 == sum2)&&(multi1 == multi2);
        
    }
    
    public static void  main(String [] args){
        Set<Integer> set1= new HashSet<Integer>();
        Set<Integer> set2= new HashSet<Integer>();
        
        set1.add(1);set1.add(3);set1.add(5);set1.add(7);set1.add(11);
        set2.add(11);set2.add(13);set2.add(5);set2.add(7);set2.add(1);
        System.out.print("=="+isEqual(set1,set2));
    }
    
    
}

原文地址:https://www.cnblogs.com/liuchuanwu/p/4741983.html